Software and Computational Systems Lab

Publications of year 2005

1. Dirk Beyer, Andreas Noack, and Claus Lewerentz. Efficient Relational Calculation for Software Analysis. IEEE Transactions on Software Engineering (TSE), 31(2):137-149, 2005. doi:10.1109/TSE.2005.23 Invited to special issue of selected papers from WCRE 2003 Keyword(s): Structural Analysis and Comprehension Publisher's Version PDF
   Abstract

   Calculating with graphs and relations has many applications in the analysis of software systems, for example, the detection of design patterns or patterns of problematic design and the computation of design metrics. These applications require an expressive query language, in particular, for the detection of graph patterns, and an efficient evaluation of the queries even for large graphs. In this paper, we introduce RML, a simple language for querying and manipulating relations based on predicate calculus, and CrocoPat, an interpreter for RML programs. RML is general because it enables the manipulation not only of graphs (i.e., binary relations), but of relations of arbitrary arity. CrocoPat executes RML programs efficiently because it internally represents relations as binary decision diagrams, a data structure that is well-known as a compact representation of large relations in computer-aided verification. We evaluate RML by giving example programs for several software analyses and CrocoPat by comparing its performance with calculators for binary relations, a Prolog system, and a relational database management system.
   BibTeX Entry

   @article{TSE05, author = {Dirk Beyer and Andreas Noack and Claus Lewerentz}, title = {Efficient Relational Calculation for Software Analysis}, journal = {IEEE Transactions on Software Engineering (TSE)}, volume = {31}, number = {2}, pages = {137-149}, year = {2005}, doi = {10.1109/TSE.2005.23}, sha256 = {}, pdf = {https://www.sosy-lab.org/research/pub/2005-TSE.Efficient_Relational_Calculation_for_Software_Analysis.pdf}, abstract = {Calculating with graphs and relations has many applications in the analysis of software systems, for example, the detection of design patterns or patterns of problematic design and the computation of design metrics. These applications require an expressive query language, in particular, for the detection of graph patterns, and an efficient evaluation of the queries even for large graphs. In this paper, we introduce RML, a simple language for querying and manipulating relations based on predicate calculus, and CrocoPat, an interpreter for RML programs. RML is general because it enables the manipulation not only of graphs (i.e., binary relations), but of relations of arbitrary arity. CrocoPat executes RML programs efficiently because it internally represents relations as binary decision diagrams, a data structure that is well-known as a compact representation of large relations in computer-aided verification. We evaluate RML by giving example programs for several software analyses and CrocoPat by comparing its performance with calculators for binary relations, a Prolog system, and a relational database management system.}, keyword = {Structural Analysis and Comprehension}, annote = {Also available as postprint at the eScholarship Repository, University of California: <BR> <a href="http://repositories.cdlib.org/postprints/687"> http://repositories.cdlib.org/postprints/687</a> <BR> CrocoPat is available at: <a href="http://www.sosy-lab.org/~dbeyer/CrocoPat/"> http://www.sosy-lab.org/~dbeyer/CrocoPat</a>}, note = {Invited to special issue of selected papers from WCRE 2003}, }
   Additional Infos

   Also available as postprint at the eScholarship Repository, University of California:
   http://repositories.cdlib.org/postprints/687
   CrocoPat is available at: http://www.sosy-lab.org/~dbeyer/CrocoPat

2. Dirk Beyer. Co-Change Visualization. In Proceedings of the 21st IEEE International Conference on Software Maintenance (ICSM 2005, Budapest, September 25-30), Industrial and Tool volume, pages 89-92, 2005. Keyword(s): Structural Analysis and Comprehension PDF Supplement
   Abstract

   Clustering layouts of software systems combine two important aspects: they reveal groups of related artifacts of the software system, and they produce a visualization of the results that is easy to understand. Co-change visualization is a lightweight method for computing clustering layouts of software systems for which the change history is available. This paper describes CCVisu, a tool that implements co-change visualization. It extracts the co-change graph from a version repository, and computes a layout, which positions the artifacts of the software system in a two- or three-dimensional space. Two artifacts are positioned closed together in the layout if they were often changed together. The tool is designed as a framework, easy to use, and easy to integrate into reengineering environments; several formats for data interchange are already implemented. The graph layout is currently provided in VRML format, in a standard text format, or directly drawn on the screen.
   BibTeX Entry

   @inproceedings{ICSM05, author = {Dirk Beyer}, title = {Co-Change Visualization}, booktitle = {Proceedings of the 21st IEEE International Conference on Software Maintenance (ICSM~2005, Budapest, September 25-30), Industrial and Tool volume}, pages = {89-92}, year = {2005}, isbn = {963-460-980-5}, url = {../../2005-ICSM.Co-Change_Visualization/main.html}, pdf = {https://www.sosy-lab.org/research/pub/2005-ICSM.Co-Change_Visualization.pdf}, abstract = {Clustering layouts of software systems combine two important aspects: they reveal groups of related artifacts of the software system, and they produce a visualization of the results that is easy to understand. Co-change visualization is a lightweight method for computing clustering layouts of software systems for which the change history is available. This paper describes CCVisu, a tool that implements co-change visualization. It extracts the co-change graph from a version repository, and computes a layout, which positions the artifacts of the software system in a two- or three-dimensional space. Two artifacts are positioned closed together in the layout if they were often changed together. The tool is designed as a framework, easy to use, and easy to integrate into reengineering environments; several formats for data interchange are already implemented. The graph layout is currently provided in VRML format, in a standard text format, or directly drawn on the screen.}, keyword = {Structural Analysis and Comprehension}, address = {Budapest}, annote = {Tool Paper <BR> CCVisu is available at: <a href="http://www.sosy-lab.org/~dbeyer/CCVisu/"> http://www.sosy-lab.org/~dbeyer/CCVisu</a>}, doinone = {DOI not available}, }
   Additional Infos

   Tool Paper
   CCVisu is available at: http://www.sosy-lab.org/~dbeyer/CCVisu
3. Dirk Beyer and Andreas Noack. Clustering Software Artifacts Based on Frequent Common Changes. In Proceedings of the 13th IEEE International Workshop on Program Comprehension (IWPC 2005, St. Louis, MO, May 15-16), pages 259-268, 2005. IEEE Computer Society Press, Los Alamitos (CA). doi:10.1109/WPC.2005.12 Keyword(s): Structural Analysis and Comprehension Publisher's Version PDF Supplement
   Abstract

   Changes of software systems are less expensive and less error-prone if they affect only one subsystem. Thus, clusters of artifacts that are frequently changed together are subsystem candidates. We introduce a two-step method for identifying such clusters. First, a model of common changes of software artifacts, called co-change graph, is extracted from the version control repository of the software system. Second, a layout of the co-change graph is computed that reveals clusters of frequently co-changed artifacts. We derive requirements for such layouts, and introduce an energy model for producing layouts that fulfill these requirements. We evaluate the method by applying it to three example systems, and comparing the resulting layouts to authoritative decompositions.
   BibTeX Entry

   @inproceedings{IWPC05, author = {Dirk Beyer and Andreas Noack}, title = {Clustering Software Artifacts Based on Frequent Common Changes}, booktitle = {Proceedings of the 13th IEEE International Workshop on Program Comprehension (IWPC~2005, St. Louis, MO, May 15-16)}, pages = {259-268}, year = {2005}, publisher = {IEEE Computer Society Press, Los Alamitos~(CA)}, isbn = {0-7695-2254-8}, doi = {10.1109/WPC.2005.12}, url = {http://www.sosy-lab.org/~dbeyer/co-change}, pdf = {https://www.sosy-lab.org/research/pub/2005-IWPC.Clustering_Software_Artifacts_Based_on_Frequent_Common_Changes.pdf}, abstract = {Changes of software systems are less expensive and less error-prone if they affect only one subsystem. Thus, clusters of artifacts that are frequently changed together are subsystem candidates. We introduce a two-step method for identifying such clusters. First, a model of common changes of software artifacts, called co-change graph, is extracted from the version control repository of the software system. Second, a layout of the co-change graph is computed that reveals clusters of frequently co-changed artifacts. We derive requirements for such layouts, and introduce an energy model for producing layouts that fulfill these requirements. We evaluate the method by applying it to three example systems, and comparing the resulting layouts to authoritative decompositions.}, keyword = {Structural Analysis and Comprehension}, annote = {Supplementary material: <a href="http://www.sosy-lab.org/~dbeyer/co-change/"> http://www.sosy-lab.org/~dbeyer/co-change/</a>}, }
   Additional Infos

   Supplementary material: http://www.sosy-lab.org/~dbeyer/co-change/
4. Dirk Beyer, Arindam Chakrabarti, and Thomas A. Henzinger. Web Service Interfaces. In Proceedings of the 14th ACM International World Wide Web Conference (WWW 2005, Chiba, May 10-14), pages 148-159, 2005. ACM Press, New York (NY). doi:10.1145/1060745.1060770 Keyword(s): Interfaces for Component-Based Design Publisher's Version PDF
   Abstract

   We present a language for specifying web service interfaces. A web service interface puts three kinds of constraints on the users of the service. First, the interface specifies the methods that can be called by a client, together with types of input and output parameters; these are called signature constraints. Second, the interface may specify propositional constraints on method calls and output values that may occur in a web service conversation; these are called consistency constraints. Third, the interface may specify temporal constraints on the ordering of method calls; these are called protocol constraints. The interfaces can be used to check, first, if two or more web services are compatible, and second, if a web service A can be safely substituted for a web service B. The algorithm for compatibility checking verifies that two or more interfaces fulfill each others' constraints. The algorithm for substitutivity checking verifies that service A demands fewer and fulfills more constraints than service B.
   BibTeX Entry

   @inproceedings{WWW05, author = {Dirk Beyer and Arindam Chakrabarti and Thomas A. Henzinger}, title = {Web Service Interfaces}, booktitle = {Proceedings of the 14th ACM International World Wide Web Conference (WWW~2005, Chiba, May 10-14)}, pages = {148-159}, year = {2005}, publisher = {ACM Press, New York~(NY)}, isbn = {1-59593-046-9}, doi = {10.1145/1060745.1060770}, url = {}, pdf = {https://www.sosy-lab.org/research/pub/2005-WWW.Web_Service_Interfaces.pdf}, abstract = {We present a language for specifying web service interfaces. A web service interface puts three kinds of constraints on the users of the service. First, the interface specifies the methods that can be called by a client, together with types of input and output parameters; these are called signature constraints. Second, the interface may specify propositional constraints on method calls and output values that may occur in a web service conversation; these are called consistency constraints. Third, the interface may specify temporal constraints on the ordering of method calls; these are called protocol constraints. The interfaces can be used to check, first, if two or more web services are compatible, and second, if a web service A can be safely substituted for a web service B. The algorithm for compatibility checking verifies that two or more interfaces fulfill each others' constraints. The algorithm for substitutivity checking verifies that service A demands fewer and fulfills more constraints than service B.}, keyword = {Interfaces for Component-Based Design}, annote = {}, }
5. Dirk Beyer, Thomas A. Henzinger, Ranjit Jhala, and Rupak Majumdar. Checking Memory Safety with Blast. In M. Cerioli, editors, Proceedings of the Eighth International Conference on Fundamental Approaches to Software Engineering (FASE 2005, Edinburgh, April 2-10), LNCS 3442, pages 2-18, 2005. Springer-Verlag, Heidelberg. doi:10.1007/978-3-540-31984-9_2 Keyword(s): BLAST, Software Model Checking Publisher's Version PDF
   Abstract

   BLAST is an automatic verification tool for checking temporal safety properties of C programs. Given a C program and a temporal safety property, BLAST statically proves that either the program satisfies the safety property or the program has an execution trace that exhibits a violation of the property. BLAST constructs, explores, and refines abstractions of the program state space based on lazy predicate abstraction and interpolation-based predicate discovery. We show how BLAST can be used to statically prove memory safety for C programs. We take a two-step approach. First, we use CCured, a type-based memory safety analyzer, to annotate with run-time checks all program points that cannot be proved memory safe by the type system. Second, we use BLAST to remove as many of the run-time checks as possible (by proving that these checks never fail), and to generate for the remaining run-time checks execution traces that witness them fail. Our experience shows that BLAST can remove many of the run-time checks added by CCured and provide useful information to the programmer about many of the remaining checks.
   BibTeX Entry

   @inproceedings{FASE05, author = {Dirk Beyer and Thomas A. Henzinger and Ranjit Jhala and Rupak Majumdar}, title = {Checking Memory Safety with {{\sc Blast}}}, booktitle = {Proceedings of the Eighth International Conference on Fundamental Approaches to Software Engineering (FASE~2005, Edinburgh, April 2-10)}, editor = {M.~Cerioli}, pages = {2-18}, year = {2005}, series = {LNCS~3442}, publisher = {Springer-Verlag, Heidelberg}, isbn = {3-540-25420-X}, doi = {10.1007/978-3-540-31984-9_2}, sha256 = {8216a41d893b4e987c3a19b82a0c8be06aa7f5bc9b35ef26ab226b95aea241b3}, url = {}, pdf = {https://www.sosy-lab.org/research/pub/2005-FASE.Checking_Memory_Safety_with_Blast.pdf}, abstract = {BLAST is an automatic verification tool for checking temporal safety properties of C programs. Given a C program and a temporal safety property, BLAST statically proves that either the program satisfies the safety property or the program has an execution trace that exhibits a violation of the property. BLAST constructs, explores, and refines abstractions of the program state space based on lazy predicate abstraction and interpolation-based predicate discovery. We show how BLAST can be used to statically prove memory safety for C programs. We take a two-step approach. First, we use CCured, a type-based memory safety analyzer, to annotate with run-time checks all program points that cannot be proved memory safe by the type system. Second, we use BLAST to remove as many of the run-time checks as possible (by proving that these checks never fail), and to generate for the remaining run-time checks execution traces that witness them fail. Our experience shows that BLAST can remove many of the run-time checks added by CCured and provide useful information to the programmer about many of the remaining checks.}, keyword = {BLAST,Software Model Checking}, annote = {}, }
6. Dirk Beyer, Arindam Chakrabarti, and Thomas A. Henzinger. An Interface Formalism for Web Services. In Proceedings of the First International Workshop on Foundations of Interface Technologies (FIT 2005, San Francisco, CA, August 21), 2005. Keyword(s): Interfaces for Component-Based Design PDF Supplement
   Abstract

   Web application development using distributed components and web services presents new software integration challenges, because solutions often cross vendor, administrative, and other boundaries across which neither binary nor source code can be shared. We present a methodology that addresses this problem through a formalism for specifying and manipulating behavioral interfaces of multi-threaded open software components that communicate with each other through method calls. An interface constrains both the implementation and the user of a web service to fulfill certain assumptions that are specified by the interface. Our methodology consists of three increasingly expressive classes of interfaces. Signature interfaces specify the methods that can be invoked by the user, together with parameters. Consistency interfaces add propositional constraints, enhancing signature interfaces with the ability to specify choice and causality. Protocol interfaces specify, in addition, temporal ordering constraints on method invocations. We provide approaches to check if two or more interfaces are compatible; if a web service can be safely substituted for another one; and if a web service satisfies a specification that represents a desired behavioral property.
   BibTeX Entry

   @inproceedings{FIT05, author = {Dirk Beyer and Arindam Chakrabarti and Thomas A. Henzinger}, title = {An Interface Formalism for Web Services}, booktitle = {Proceedings of the First International Workshop on Foundations of Interface Technologies (FIT~2005, San Francisco, CA, August 21)}, pages = {}, year = {2005}, isbn = {}, url = {http://infoscience.epfl.ch/search?recid=114605&ln=en}, pdf = {https://www.sosy-lab.org/research/pub/2007-EPFL-TR002.An_Interface_Formalism_for_Web_Services.pdf}, abstract = {Web application development using distributed components and web services presents new software integration challenges, because solutions often cross vendor, administrative, and other boundaries across which neither binary nor source code can be shared. We present a methodology that addresses this problem through a formalism for specifying and manipulating behavioral interfaces of multi-threaded open software components that communicate with each other through method calls. An interface constrains both the implementation and the user of a web service to fulfill certain assumptions that are specified by the interface. Our methodology consists of three increasingly expressive classes of interfaces. Signature interfaces specify the methods that can be invoked by the user, together with parameters. Consistency interfaces add propositional constraints, enhancing signature interfaces with the ability to specify choice and causality. Protocol interfaces specify, in addition, temporal ordering constraints on method invocations. We provide approaches to check if two or more interfaces are compatible; if a web service can be safely substituted for another one; and if a web service satisfies a specification that represents a desired behavioral property.}, keyword = {Interfaces for Component-Based Design}, annote = {}, doinone = {DOI not available}, }

7. Dirk Beyer, Thomas A. Henzinger, and Grégory Théoduloz. Lazy Shape Analysis. Technical report MTC-REPORT-2005-006, School of Computer and Communication Sciences (IC), Ecole Polytechnique Féd́̊ale de Lausanne (EPFL), December 2005. Keyword(s): Software Model Checking PDF Supplement
   Abstract

   Many software model checkers are based on predicate abstraction. Values of variables in branching conditions are represented abstractly using predicates. The strength of this approach is its path-sensitive nature. However, if the control flow depends heavily on the values of memory cells on the heap, the approach does not work well, because it is difficult to find 'good' predicate abstractions to represent the heap. In contrast, shape analysis can lead to a very compact representation of data structures stored on the heap. In this paper, we combine shape analysis with predicate abstraction, and integrate it into the software model checker BLAST. Because shape analysis is expensive, we do not apply it globally. Instead, we ensure that shapes are computed and stored locally, only where necessary for proving the verification goal. To achieve this, we extend lazy abstraction refinement, which so far has been used only for predicate abstractions, to shapes. This approach does not only increase the precision of model checking and shape analysis taken individually, but also increases the efficiency of shape analysis (we do not compute shapes where not necessary). We implemented the technique by extending BLAST with calls to TVLA, and evaluated it on several C programs manipulating data structures, with the result that the combined tool can now automatically verify programs that are not verifiable using either shape analysis or predicate abstraction on its own.
   BibTeX Entry

   @techreport{TR006-EPFL05, author = {Dirk Beyer and Thomas A.~Henzinger and Gr{\'e}gory Th{\'e}oduloz}, title = {Lazy Shape Analysis}, number = {MTC-REPORT-2005-006}, year = {2005}, url = {http://infoscience.epfl.ch/search.py?recid=63789&ln=en}, pdf = {https://www.sosy-lab.org/research/pub/2005-EPFL-TR006.Lazy_Shape_Analysis.pdf}, abstract = {Many software model checkers are based on predicate abstraction. Values of variables in branching conditions are represented abstractly using predicates. The strength of this approach is its path-sensitive nature. However, if the control flow depends heavily on the values of memory cells on the heap, the approach does not work well, because it is difficult to find `good' predicate abstractions to represent the heap. In contrast, shape analysis can lead to a very compact representation of data structures stored on the heap. In this paper, we combine shape analysis with predicate abstraction, and integrate it into the software model checker BLAST. Because shape analysis is expensive, we do not apply it globally. Instead, we ensure that shapes are computed and stored locally, only where necessary for proving the verification goal. To achieve this, we extend lazy abstraction refinement, which so far has been used only for predicate abstractions, to shapes. This approach does not only increase the precision of model checking and shape analysis taken individually, but also increases the efficiency of shape analysis (we do not compute shapes where not necessary). We implemented the technique by extending BLAST with calls to TVLA, and evaluated it on several C programs manipulating data structures, with the result that the combined tool can now automatically verify programs that are not verifiable using either shape analysis or predicate abstraction on its own.}, keyword = {Software Model Checking}, annote = {Online: <a href="http://infoscience.epfl.ch/search.py?recid=63789&ln=en"> http://infoscience.epfl.ch/search.py?recid=63789&ln=en</a> <BR>}, institution = {School of Computer and Communication Sciences (IC), Ecole Polytechnique F\'ed\'erale de Lausanne (EPFL)}, month = {December}, }
   Additional Infos

   Online: http://infoscience.epfl.ch/search.py?recid=63789&ln=en
   
8. Dirk Beyer and Andreas Noack. Mining Co-Change Clusters from Version Repositories. Technical report IC/2005/003, School of Computer and Communication Sciences (IC), Ecole Polytechnique Féd́̊ale de Lausanne (EPFL), January 2005. Keyword(s): Structural Analysis and Comprehension PDF Supplement
   Abstract

   Clusters of software artifacts that are frequently changed together are subsystem candidates, because one of the main goals of software design is to make changes local. The contribution of this paper is a visualization-based method that supports the identification of such clusters. First, we define the co-change graph as a simple but powerful model of common changes of software artifacts, and describe how to extract the graph from version control repositories. Second, we introduce an energy model for computing force-directed layouts of co-change graphs. The resulting layouts have a well-defined interpretation in terms of the structure of the visualized graph, and clearly reveal groups of frequently co-changed artifacts. We evaluate our method by comparing the layouts for three example projects with authoritative subsystem decompositions.
   BibTeX Entry

   @techreport{TR003-EPFL05, author = {Dirk Beyer and Andreas Noack}, title = {Mining Co-Change Clusters from Version Repositories}, number = {IC/2005/003}, year = {2005}, url = {http://infoscience.epfl.ch/record/52706}, pdf = {https://www.sosy-lab.org/research/pub/2005-EPFL-TR003.Mining_Co-Change_Clusters_from_Version_Repositories.pdf}, abstract = {Clusters of software artifacts that are frequently changed together are subsystem candidates, because one of the main goals of software design is to make changes local. The contribution of this paper is a visualization-based method that supports the identification of such clusters. First, we define the co-change graph as a simple but powerful model of common changes of software artifacts, and describe how to extract the graph from version control repositories. Second, we introduce an energy model for computing force-directed layouts of co-change graphs. The resulting layouts have a well-defined interpretation in terms of the structure of the visualized graph, and clearly reveal groups of frequently co-changed artifacts. We evaluate our method by comparing the layouts for three example projects with authoritative subsystem decompositions.}, keyword = {Structural Analysis and Comprehension}, annote = {Online: <a href="http://infoscience.epfl.ch/record/52706"> http://infoscience.epfl.ch/record/52706</a> <BR>}, institution = {School of Computer and Communication Sciences (IC), Ecole Polytechnique F\'ed\'erale de Lausanne (EPFL)}, month = {January}, }
   Additional Infos

   Online: http://infoscience.epfl.ch/record/52706
   

9. CCVisu: Visual Clustering and Software-Structure Assessment. 2005. Keyword(s): Software Development Project, Structural Analysis and Comprehension Supplement
   BibTeX Entry

   @misc{CCVisu, title = {{{\sc CCVisu}}: Visual Clustering and Software-Structure Assessment}, year = {2005}, url = {http://www.sosy-lab.org/~dbeyer/CCVisu/}, keyword = {Software Development Project,Structural Analysis and Comprehension}, role = {Principal designer and implementer}, }