We extend previous depedence-based representations called system dependence graphs (SDGs) to represent aspect-oriented programs and present an SDG construction algorithm. This algorithm first constructs a module dependence graph (MDG) for each piece of advice, introduction, and method in aspects and classes. It then uses existing techniques to connect the MDGs at call sites to form a partial SDG. Finally, it weaves the MDG for each eice of advice into the partial SDG for those methods whose behavior may be affected by the ad-vice. The result is the complete SDG. Our SDGs capture the additional structure present in many as pect-oriented fea-tures such as join points, advice, introuduction, aspects, and aspect in heritance, and various types of interactions between aspects and classes. They also correctly reflect the semantics of aspect-oriented concepts such as advice precedence, intro-duction scope, and aspect weaving. SDGs therefore provide a solid foundation for the further analysis of aspect-oriented programs.