Christian Kästner

[pronunciation and spelling]

Assistant Professor · Carnegie Mellon University · Institute for Software Research

 
Christian Kästner

I am an assistant professor in the Institute of Software Research at the Carnegie Mellon University interested in controlling the complexity caused by variability in software systems. I develop mechanisms, languages, and tools to implement variability in a disciplined way, to detect errors, and to improve program comprehension in systems with a high amount of variability. Currently, I investigate approaches to parse and type check all compile-time configurations of the Linux kernel in the TypeChef project.

My research in keywords: variability and reuse; software product lines; multidimensional separation of concerns; modularity, cohesion, information hiding and module systems; program comprehension; virtual separation of concerns; feature-oriented software development; parsers, type systems, and lightweight program analyses; refactoring; aspect-orientation; program synthesis; feature interactions; feature location; Linux; and empirical methods.

Profiles: Curriculum vitae, Google Scholar, ACM, dblp, Google+ .

Institute for Software Research (Link)
School of Computer Science (Link)
Carnegie Mellon University (Link)
5000 Forbes Avenue, Pittsburgh, PA 15213, USA
 
Office: Wean 5122
 
E-mail: kaestner (at) cs.cmu.edu
Phone: +1 412 268 5254

 
 
 

News News feed

 
2 Jul. 2014
Teaching Software Construction with Travis CI
We had great experiences introducing continuous integration tools into our software construction course using Travis CI and I've been meaning to write down our experience for a while now. I finally got around doing that: Teaching Software Construction with Travis CI. Feedback is welcome.
 
10 May. 2014
FOSD Meeting 2015
The FOSD Meeting 2014 last week in Dagstuhl was great fun. Thanks for everybody who came, presented, and discussed. We have already started planning for 2015. We will be in Austria in Traunkirchen the week before ICSE. We will likely expand it to a 4.5 day meeting for up to 50 participants, with social events and keynotes. Looking forward to seeing you all there.
 
27 Mar. 2014
Research Experiences for Undergraduates in Software Engineering
We are looking for a number of undergraduate students who would be interested in doing software-engineering research at CMU this summer. I'd be interested in working with somebody on several of my projects (around TypeChef, Github, or Energy Measurements). If you might be interested spending the summer in Pittsburgh, please consider applying. See our REU-SE website for projects and details.
 
 
Older News...
 
 
 

Teaching

 
Fall 2014
 
Spring 2014
 
Fall 2013
 
Spring 2013
 
Summer 2012
 
Summer 2011
 
Winter 2010/11
 
 
See also the full teaching history.
 
 
 

Team

 
Current PhD students
 
Close external collaborations / coadvising
 
Visiting students
 
 
 

Committees

ASE 2015 (PC), SPLC 2014 (PC), ASE 2014 (PC), ECOOP 2014 (ERC), MV 2014 (PC), GPCE 2014 (SC), OOPSLA 2013 (PC), GPCE 2013 (PC Chair), SE 2013 (PC), GPCE 2012 (PC), SC 2011 (PC), GPCE 2011 (PC)
 
VaMoS 2015 (PC), ICSE-D 2015 (PC), MultiPLE 2014 (PC), SPLat 2014 (PC), SPLTea 2014 (PC), REVE 2014 (PC), FOSD 2014 (OC), ICSE-TB 2014 (PC), VaMoS 2014 (PC), SCORE 2013 (PC), MPLE 2013 (PC), FOSD 2013 (OC), VaMoS 2013 (PC), REVE 2013 (PC), SLE-DS 2012 (PC), FOSD 2012 (OC), SPLC-TD 2012 (PC), NFPinDSML 2012 (PC), RAM-SE 2012 (PC), ESCOT 2012 (OC), MISS 2012 (PC), PEPM 2012 (PC), VaMoS 2012 (PC), FOSD 2011 (OC), FREECO 2011 (PC), FOSD 2010 (OC), ASE-TD 2010 (PC), PLEERPS 2010 (PC), FOSD 2009 (OC)
 
 
 

Grants & Awards

 
Jun. 2013
Grant: Reverse Engineering Variability Implementations National Science Foundation. Sep. 2013 – Aug. 2016
 
Jun. 2012
Grant: Pythia – Techniques and Prediction Models for Sustainable Product-Line Engineering German Research Foundation. Oct. 2012 – Oct. 2015
 
Oct. 2011
GI-Dissertationspreis: Best Dissertation Award of the German Computer Science Association, 2010 (Annoucement, Photo)
 
Oct. 2011
Distinguished-Paper Award at the International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA) 2011 (Photo)
 
Aug. 2011
Best-Research-Paper Award at the International Software Product Line Conference 2011
 
Nov. 2010
Best-Dissertation Award of the School of Computer Science, University of Magdeburg, 2010
 
Dec. 2009
Research Award of the School of Computer Science, University of Magdeburg for the Best Paper, 2009
 
Sep. 2007
Software Engineering Award of the Denert Foundation for the Best Master's Thesis, 2007 (Photo)
 
Oct. 2007
Best-Graduate Award of the School of Computer Science, University of Magdeburg, 2007 (Photo)
 
Sep. 2006
Student Scholarship of the Germany Academic Exchange Service
 
 
 

Research Projects & Software

 
TypeChef
Variability-Aware Analysis and Parsing of C Code
 
Feature Mining
Consistent Semi-Automatic Detection of Product-Line Features
 
CIDE
Virtual Separation of Concerns
 
SugarJ
Library-based Syntactic Language Extensibility
 
FeatureIDE
Tool Support for Feature-Oriented Software Development
 
FeatureHouse
Language-Independent, Automatic Software Composition
 
FAME-DBMS
Tailor-Made Data Management (finished)
 
ARJ
Extending AspectJ with Aspect Refinement and Mixin-Based Aspect Inheritance (finished)
 
 
 

Key Publications Full publication feed

For a complete list of publications, see the publication page.

 
ASE 2014
M. Lillack, C. Kästner, and E. Bodden. Tracking Load-time Configuration Options. In Proceedings of the 29th IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 445--456, Los Alamitos, CA: IEEE Computer Society, September 2014. Acceptance rate: 20 % (55/276). [ .pdf, doi, bib ]

Highly-configurable software systems are pervasive, although configuration options and their interactions raise complexity of the program and increase maintenance effort. Especially load-time configuration options, such as parameters from command-line options or configuration files, are used with standard programming constructs such as variables and if statements intermixed with the program’s implementation; manually tracking configuration options from the time they are loaded to the point where they may influence control-flow decisions is tedious and error prone. We design and implement Lotrack, an extended static taint analysis to automatically track configuration options. Lotrack derives a configuration map that explains for each code fragment under which configurations it may be executed. An evaluation on Android applications shows that Lotrack yields high accuracy with reasonable performance. We use Lotrack to empirically characterize how much of the implementation of Android apps depends on the platform’s configuration options or interactions of these options.

 
FSE 2014
H. Nguyen, C. Kästner, and T. Nguyen. Building Call Graphs for Embedded Client-Side Code in Dynamic Web Applications. In Proceedings of the ACM SIGSOFT Symposium on the Foundations of Software Engineering (FSE), New York, NY: ACM Press, November 2014. Acceptance rate: 22 % (61/273). [ .pdf, bib ]

When developing and maintaining a software system, programmers often rely on IDEs to provide editor services such as syntax highlighting, auto-completion, and “jump to declaration”. In dynamic web applications, such tool support is currently limited to either the server-side code or to hand-written or generated client-side code. Our goal is to build a call graph for providing editor services on client-side code while it is still embedded as string literals within server-side code. First, we symbolically execute the server-side code to identify all possible client-side code variations. Subsequently, we parse the generated client-side code with all its variations into a VarDOM that compactly represents all DOM variations for further analysis. Based on VarDOM, we build conditional call graphs for embedded HTML, CSS, and JS. Our empirical evaluation on real-world web applications show that our analysis achieves 100 % precision in identifying call-graph edges. 62 % of the edges cross PHP strings, and 17 % of them cross files—in both situations, navigation without tool support is tedious and error prone.

 
Onward! 2014
E. Walkingshaw, C. Kästner, M. Erwig, S. Apel, and E. Bodden. Variational Data Structures: Exploring Tradeoffs in Computing with Variability. In Proceedings of the 13rd SIGPLAN Symposium on New Ideas in Programming and Reflections on Software at SPLASH (Onward!), pages 213--226, New York, NY: ACM Press, 2014. [ .pdf, doi, bib ]

Variation is everywhere, but in the construction and analysis of customizable software it is paramount. In this context, there arises a need for variational data structures for efficiently representing and computing with related variants of an underlying data type. So far, variational data structures have been explored and developed ad hoc. This paper is a first attempt and a call to action for systematic and foundational research in this area. Research on variational data structures will benefit not only customizable software, but the many other application domains that must cope with variability. In this paper, we show how support for variation can be understood as a general and orthogonal property of data types, data structures, and algorithms. We begin a systematic exploration of basic variational data structures, exploring the tradeoffs between different implementations. Finally, we retrospectively analyze the design decisions in our own previous work where we have independently encountered problems requiring variational data structures.

 
CSUR 2014
T. Thüm, S. Apel, C. Kästner, I. Schaefer, and G. Saake. A Classification and Survey of Analysis Strategies for Software Product Lines. ACM Computing Surveys (CSUR), 47(1):Article 6, June 2014. [ .pdf, http, doi, bib ]

Software-product-line engineering has gained considerable momentum in recent years, both in industry and in academia. A software product line is a set of software products that share a common set of features. Software product lines challenge traditional analysis techniques, such as type checking, model checking, and theorem proving, in their quest of ensuring correctness and reliability of software. Simply creating and analyzing all products of a product line is usually not feasible, due to the potentially exponential number of valid feature combinations. Recently, researchers began to develop analysis techniques that take the distinguishing properties of software product lines into account, for example, by checking feature-related code in isolation or by exploiting variability information during analysis. The emerging field of product-line analyses is both broad and diverse, such that it is difficult for researchers and practitioners to understand their similarities and differences. We propose a classification of product-line analyses to enable systematic research and application. Based on our insights with classifying and comparing a corpus of 76 articles, we infer a research agenda to guide future research on product-line analyses.

 
ICSE 2014
J. Siegmund, C. Kästner, S. Apel, C. Parnin, A. Bethmann, T. Leich, G. Saake, and A. Brechmann. Understanding Understanding Source Code with Functional Magnetic Resonance Imaging. In Proceedings of the 36th International Conference on Software Engineering (ICSE), pages 378--389, June 2014. Acceptance rate: 20 % (99/495). [ .pdf, doi, bib ]

Program comprehension is an important cognitive process that inherently eludes direct measurement. Thus, researchers are struggling with providing optimal programming languages, tools, or coding conventions to support developers in their everyday work. With our approach, we explore whether functional magnetic resonance imaging (fMRI), which is well established in cognitive neuroscience, is feasible to directly measure program comprehension. To this end, we observed 17 participants inside an fMRI scanner while comprehending short source-code snippets, which we contrasted with locating syntax errors. We found a clear, distinct activation pattern of five brain regions, which are related to working memory, attention, and language processing—all processes that fit well to our understanding of program comprehension. Based on the results, we propose a model of program comprehension. Our results encourage us to use fMRI in future studies to measure program comprehension and, in the long run, answer questions, such as: Can we predict whether someone will be an excellent programmer? How effective are new languages and tools for program understanding? How do we train someone to become an excellent programmer?

 
ICSE 2014
H. Nguyen, C. Kästner, and T. Nguyen. Exploring Variability-Aware Execution for Testing Plugin-Based Web Applications. In Proceedings of the 36th International Conference on Software Engineering (ICSE), pages 907--918, June 2014. Acceptance rate: 20 % (99/495). [ .pdf, doi, bib ]

In plugin-based systems, plugin conflicts may occur when two or more plugins interfere with one another, changing their expected behaviors. It is highly challenging to detect plugin conflicts due to the exponential explosion of the combinations of plugins (i.e., configurations). In this paper, we address the challenge of executing a test case over many configurations. Leveraging the fact that many executions of a test are similar, our variability-aware execution runs common code once. Only when encountering values that are different depending on specific configurations will the execution split to run for each of them. To evaluate the scalability of variability-aware execution on a large real-world setting, we built a prototype PHP interpreter called Varex and ran it on the popular WordPress blogging Web application. The results show that while plugin interactions exist, there is a significant amount of sharing that allows variability-aware execution to scale to 2^50 configurations within seven minutes of running time. During our study, with Varex, we were able to detect two plugin conflicts: one was recently reported on WordPress forum, and another one is not yet discovered.

 
ICSE 2014
S. Nadi, T. Berger, C. Kästner, and K. Czarnecki. Mining Configuration Constraints: Static Analyses and Empirical Results. In Proceedings of the 36th International Conference on Software Engineering (ICSE), pages 140--151, June 2014. Acceptance rate: 20 % (99/495). [ .pdf, doi, bib ]

Highly-configurable systems allow users to tailor the software to their specific needs. Not all combinations of configuration options are valid though, and constraints arise for technical or non-technical reasons. Explicitly describing these constraints in a variability model allows reasoning about the supported configurations. To automate creating variability models, we need to identify the origin of such configuration constraints. We propose an approach which uses build-time errors and a novel feature-effect heuristic to automatically extract configuration constraints from C code. We conduct an empirical study on four highly-configurable open-source systems with existing variability models having three objectives in mind: evaluate the accuracy of our approach, determine the recoverability of existing variability-model constraints using our analysis, and classify the sources of variability-model constraints. We find that both our extraction heuristics are highly accurate (93 % and 77 % respectively), and that we can recover 19 % of the existing variability-models using our approach. However, we find that many of the remaining constraints require expert knowledge or more expensive analyses. We argue that our approach, tooling, and experimental results support researchers and practitioners working on variability model re-engineering, evolution, and consistency-checking techniques.

 
ICSE 2014
M. Ribeiro, P. Borba, and C. Kästner. Feature Maintenance with Emergent Interfaces. In Proceedings of the 36th International Conference on Software Engineering (ICSE), pages 989--1000, June 2014. Acceptance rate: 20 % (99/495). [ .pdf, doi, bib ]

Hidden code dependencies are responsible for many complications in maintenance tasks. With the introduction of variable features in product lines, dependencies may even cross feature boundaries and related problems are prone to be detected late. Many current implementation techniques for product lines lack proper interfaces, which could make such dependencies explicit. As alternative to changing the implementation approach, we provide a comprehensive tool-based solution to support developers in recognizing and dealing with feature dependencies: emergent interfaces. Emergent interfaces are computed on demand, based on feature-sensitive interprocedural data-flow analysis. They emerge in the IDE and emulate benefits of modularity not available in the host language. To evaluate the potential of emergent interfaces, we conducted and replicated a controlled experiment, and found, in the studied context, that emergent interfaces can improve performance of code change tasks by up to 3 times while also reducing the number of errors.

 
TSE 2014
C. Kästner, A. Dreiling, and K. Ostermann. Variability Mining: Consistent Semiautomatic Detection of Product-Line Features. IEEE Transactions on Software Engineering (TSE), 40(1):67--82, 2014. [ .pdf, doi, http, bib ]

Software product line engineering is an efficient means to generate a set of tailored software products from a common implementation. However, adopting a product-line approach poses a major challenge and significant risks, since typically legacy code must be migrated toward a product line. Our aim is to lower the adoption barrier by providing semiautomatic tool support—called variability mining—to support developers in locating, documenting, and extracting implementations of product-line features from legacy code. Variability mining combines prior work on concern location, reverse engineering, and variability-aware type systems, but is tailored specifically for the use in product lines. Our work pursues three technical goals: (1) we provide a consistency indicator based on a variability-aware type system, (2) we mine features at a fine level of granularity, and (3) we exploit domain knowledge about the relationship between features when available. With a quantitative study, we demonstrate that variability mining can efficiently support developers in locating features.

 
ESEC/FSE 2013
J. Liebig, A. von Rhein, C. Kästner, S. Apel, J. Dörre, and C. Lengauer. Scalable Analysis of Variable Software. In Proceedings of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE), pages 81--91, New York, NY: ACM Press, August 2013. Acceptance rate: 20 % (51/251). [ .pdf, doi, http, bib ]

The advent of proper variability management and generator technology enables users to derive individual variants from a variable code base solely based on a selection of desired configuration options. This approach gives rise to a huge configuration space, but the high degree of variability comes at a cost: classic analysis methods do not scale any more; there are simply too many potential variants to analyze. To address this issue, researchers and practitioners usually apply sampling techniques—only a subset of all possible variants is analyzed. While sampling promises to reduce the analysis effort significantly, the information obtained is necessarily incomplete. Furthermore, it is unknown whether sampling strategies scale to billions of variants, because even samples may be huge and expensive to compute. Recently, researchers have begun to develop variability-aware analyses that analyze the variable code base directly with the goal to exploit the similarities among individual variants to reduce analysis effort. However, while being promising, so far, variability-aware analyses have been applied mostly only to small academic systems. To learn about the mutual strengths and weaknesses of variability-aware and sampling-based analyses of large-scale, real-world software systems, we compared the two by means of two concrete analysis implementations (type checking and liveness analysis) applied to three subject systems: the Busybox tool suite, the x86 Linux kernel, and the cryptographic library OpenSSL. A key result is that in these settings already setting up sampling techniques is challenging while variability-aware analysis even outperforms most sampling approximations with respect to analysis time.

 
2013
S. Apel, D. Batory, C. Kästner, and G. Saake. Feature-Oriented Software Product Lines: Concepts and Implementation. Berlin/Heidelberg: Springer-Verlag, 2013. 308 pages, ISBN 978-3-642-37520-0. [ http, bib ]

While standardization has empowered the software industry to substantially scale software development and to provide affordable software to a broad market, it often does not address smaller market segments, nor the needs and wishes of individual customers. Software product lines reconcile mass production and standardization with mass customization in software engineering. Ideally, based on a set of reusable parts, a software manufacturer can generate a software product based on the requirements of its customer. The concept of features is central to achieving this level of automation, because features bridge the gap between the requirements the customer has and the functionality a product provides. Thus features are a central concept in all phases of product-line development. The authors take a developer’s viewpoint, focus on the development, maintenance, and implementation of product-line variability, and especially concentrate on automated product derivation based on a user’s feature selection. The book consists of three parts. Part I provides a general introduction to feature-oriented software product lines, describing the product-line approach and introducing the product-line development process with its two elements of domain and application engineering. The pivotal Part II covers a wide variety of implementation techniques including design patterns, frameworks, components, feature-oriented programming, and aspect-oriented programming, as well as tool-based approaches including preprocessors, build systems, version-control systems, and virtual separation of concerns. Finally, Part III is devoted to advanced topics related to feature-oriented product lines like refactoring, feature interaction, and analysis tools specific to product lines. In addition, an Appendix lists various helpful tools for software product-line development, along with a description of how they relate to the topics covered in this book. To tie the book together, the authors use two running examples that are well documented in the product-line literature: data management for embedded systems, and variations of graph data structures. They start every chapter by explicitly stating the respective learning goals and finish it with a set of exercises; additional teaching material is also available online. All these features make the book ideally suited for teaching – both for academic classes and for professionals interested in self-study.

 
OOPSLA 2012
C. Kästner, K. Ostermann, and S. Erdweg. A Variability-Aware Module System. In Proceedings of the 27th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), pages 773--792, New York, NY: ACM Press, October 2012. Acceptance rate: 25 % (57/228). [ .pdf, doi, bib ]

Module systems enable a divide and conquer strategy to software development. To implement compile-time variability in software product lines, modules can be composed in different combinations. However, this way variability dictates a dominant decomposition. Instead, we introduce a variability-aware module system that supports compile-time variability inside a module and its interface. This way, each module can be considered a product line that can be type checked in isolation. Variability can crosscut multiple modules. The module system breaks with the antimodular tradition of a global variability model in product-line development and provides a path toward software ecosystems and product lines of product lines developed in an open fashion. We discuss the design and implementation of such a module system on a core calculus and provide an implementation for C, which we use to type check the open source product line Busybox with 811 compile-time options.

 
ESE 2012
J. Feigenspan, C. Kästner, S. Apel, J. Liebig, M. Schulze, R. Dachselt, M. Papendieck, T. Leich, and G. Saake. Do Background Colors Improve Program Comprehension in the #ifdef Hell? Empirical Software Engineering (ESE), 18(4):699--745, 2012. [ .pdf, http, doi, bib ]

Software-product-line engineering aims at the development of variable and reusable software systems. In practice, software product lines are often implemented with preprocessors. Preprocessor directives are easy to use, and many mature tools are available for practitioners. However, preprocessor directives have been heavily criticized in academia and even referred to as “#ifdef hell”, because they introduce threats to program comprehension and correctness. There are many voices that suggest to use other implementation techniques instead, but these voices ignore the fact that a transition from preprocessors to other languages and tools is tedious, erroneous, and expensive in practice. Instead, we and others propose to increase the readability of preprocessor directives by using background colors to highlight source code annotated with ifdef directives. In three controlled experiments with over 70 subjects in total, we evaluate whether and how background colors improve program comprehension in preprocessor-based implementations. Our results demonstrate that background colors have the potential to improve program comprehension, independently of size and programming language of the underlying product. Additionally, we found that subjects generally favor background colors. We integrate these and other findings in a tool called FeatureCommander, which facilitates program comprehension in practice and which can serve as a basis for further research.

 
ICSE 2012
N. Siegmund, S. Kolesnikov, C. Kästner, S. Apel, D. Batory, M. Rosenmüller, and G. Saake. Predicting Performance via Automated Feature-Interaction Detection. In Proceedings of the 34th International Conference on Software Engineering (ICSE), pages 167--177, Los Alamitos, CA: IEEE Computer Society, 2012. Acceptance rate: 21 % (87/408). [ .pdf, bib ]

Customizable programs and program families provide user-selectable features to tailor a program to an application scenario. Knowing in advance which feature selection yields the best performance is difficult because a direct measurement of all possible feature combinations is infeasible. Our work aims at predicting program performance based on selected features. The challenge is predicting performance accurately when features interact. An interaction occurs when a feature combination has an unexpected influence on performance. We present a method that automatically detects performance feature interactions to improve prediction accuracy. To this end, we propose three heuristics to reduce the number of measurements required to detect interactions. Our evaluation consists of six real-world case studies from varying domains (e.g. databases, compression libraries, and web server) using different configuration techniques (e.g., configuration files and preprocessor flags). Results show, on average, a prediction accuracy of 95 %.

 
TSE 2013
S. Apel, C. Kästner, and C. Lengauer. Language-Independent and Automated Software Composition: The FeatureHouse Experience. IEEE Transactions on Software Engineering (TSE), 39(1):63--79, 2013. [ .pdf, http, bib ]

Superimposition is a composition technique that has been applied successfully in many areas of software development. Although superimposition is a general-purpose concept, it has been (re)invented and implemented individually for various kinds of software artifacts. We unify languages and tools that rely on superimposition by using the language-independent model of feature structure trees (FSTs). On the basis of the FST model, we propose a general approach to the composition of software artifacts written in different languages. Furthermore, we offer a supporting framework and tool chain, called FeatureHouse. We use attribute grammars to automate the integration of additional languages. In particular, we have integrated Java, C#, C, Haskell, Alloy, and JavaCC. A substantial number of case studies demonstrate the practicality and scalability of our approach and reveal insights into the properties that a language must have in order to be ready for superimposition. We discuss perspectives of our approach and demonstrate how we extended FeatureHouse with support for XML languages (in particular, XHTML, XMI/UML, and Ant) and alternative composition approaches (in particular, aspect weaving). Rounding off our previous work, we provide here a holistic view of the FeatureHouse approach based on rich experience with numerous languages and case studies and reflections on several years of research.

 
FOSD 2011
C. Kästner, S. Apel, and K. Ostermann. The Road to Feature Modularity? In Proceedings of the 3rd International Workshop on Feature-Oriented Software Development (FOSD), pages 5:1--5:8, New York, NY: ACM Press, September 2011. [ doi, .pdf, bib ]

Modularity of feature representations has been a long standing goal of feature-oriented software development. While some researchers regard feature modules and corresponding composition mechanisms as a modular solution, other researchers have challenged the notion of feature modularity and pointed out that most feature-oriented implementation mechanisms lack proper interfaces and support neither modular type checking nor separate compilation. We step back and reflect on the feature-modularity discussion. We distinguish two notions of modularity, cohesion without interfaces and information hiding with interfaces, and point out the different expectations that, we believe, are the root of many heated discussions. We discuss whether feature interfaces should be desired and weigh their potential benefits and costs, specifically regarding crosscutting, granularity, feature interactions, and the distinction between closed-world and open-world reasoning. Because existing evidence for and against feature modularity and feature interfaces is shaky and inconclusive, more research is needed, for which we outline possible directions.

 
OOPSLA 2011
C. Kästner, P. Giarrusso, T. Rendel, S. Erdweg, K. Ostermann, and T. Berger. Variability-Aware Parsing in the Presence of Lexical Macros and Conditional Compilation. In Proceedings of the 26th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), pages 805--824, New York, NY: ACM Press, October 2011. Acceptance rate: 37 % (61/166). [ doi, .pdf, bib ]

In many projects, lexical preprocessors are used to manage different variants of the project (using conditional compilation) and to define compile-time code transformations (using macros). Unfortunately, while being a simply way to implement variability, conditional compilation and lexical macros hinder automatic analysis, even though such analysis would be urgently needed to combat variability-induced complexity. To analyze code with its variability, we need to parse it without preprocessing it. However, current parsing solutions use heuristics, support only a subset of the language, or suffer from exponential explosion. As part of the TypeChef project, we contribute a novel variability-aware parser that can parse unpreprocessed code without heuristics in practicable time. Beyond the obvious task of detecting syntax errors, our parser paves the road for further analysis, such as variability-aware type checking. We implement variabilityaware parsers for Java and GNU C and demonstrate practicability by parsing the product line MobileMedia and the entire X86 architecture of the Linux kernel with 6065 variable features.

 
ECOOP 2011
K. Ostermann, P. Giarrusso, C. Kästner, and T. Rendel. Revisiting Information Hiding: Reflections on Classical and Nonclassical Modularity. In Proceedings of the 25th European Conference on Object-Oriented Programming (ECOOP), volume 6813 of Lecture Notes in Computer Science, pages 155--178, Berlin/Heidelberg: Springer-Verlag, 2011. Acceptance rate: 26 % (26/100). [ doi, .pdf, epub, bib ]

What is modularity? Which kind of modularity should developers strive for? Despite decades of research on modularity, these basic questions have no definite answer. We submit that the common understanding of modularity, and in particular its notion of information hiding, is deeply rooted in classical logic. We analyze how classical modularity, based on classical logic, fails to address the needs of developers of large software systems, and encourage researchers to explore alternative visions of modularity, based on nonclassical logics, and henceforth called nonclassical modularity.

 
TOSEM 2012
C. Kästner, S. Apel, T. Thüm, and G. Saake. Type Checking Annotation-Based Product Lines. ACM Transactions on Software Engineering and Methodology (TOSEM), 21(3):Article 14, 2012. [ .pdf, epub, doi, bib ]

Software-product-line engineering is an efficient means to generate a family of program variants for a domain from a single code base. However, because of the potentially high number of possible program variants, it is difficult to test them all and ensure properties like type safety for the entire product line. We present a product-line–aware type system that can type check an entire software product line without generating each variant in isolation. Specifically, we extend the Featherweight Java calculus with feature annotations for product-line development and prove formally that all program variants generated from a well-typed product line are well-typed. Furthermore, we present a solution to the problem of typing mutually exclusive features. We discuss how results from our formalization helped implementing our own product-line tool CIDE for full Java and report of experience with detecting type errors in four existing software-product-line implementations.

 
AOSD 2011
J. Liebig, C. Kästner, and S. Apel. Analyzing the Discipline of Preprocessor Annotations in 30 Million Lines of C Code. In Proceedings of the 10th ACM International Conference on Aspect-Oriented Software Development (AOSD), pages 191--202, New York, NY: ACM Press, March 2011. Acceptance rate: 23 % (21/92). [ .pdf, acm, bib ]

The C preprocessor cpp is a widely used tool for implementing variable software. It enables programmers to express variable code of features that may crosscut the entire implementation with conditional compilation. The C preprocessor relies on simple text processing and is independent of the host language (C, C++, Java, and so on). Language independent text processing is powerful and expressive|programmers can make all kinds of annotations in the form of #ifdefs but can render unpreprocessed code difficult to process automatically by tools, such as code aspect refactoring, concern management, and also static analysis and variability-aware type checking. We distinguish between disciplined annotations, which align with the underlying source-code structure, and undisciplined annotations, which do not align with the structure and hence complicate tool development. This distinction raises the question of how frequently programmers use undisciplined annotations and whether it is feasible to change them to disciplined annotations to simplify tool development and to enable programmers to use a wide variety of tools in the first place. By means of an analysis of 40 mediumsized to large-sized C programs, we show empirically that programmers use cpp mostly in a disciplined way: about 85 % of all annotations respect the underlying source-code structure. Furthermore, we analyze the remaining undisciplined annotations, identify patterns, and discuss how to transform them into a disciplined form.

 
2010
C. Kästner. Virtual Separation of Concerns: Toward Preprocessors 2.0. PhD thesis, Magdeburg, Germany: University of Magdeburg, May 2010. Logos Verlag Berlin, isbn 978-3-8325-2527-9. [ doi, http, .pdf, bib ]

Conditional compilation with preprocessors such as cpp is a simple but effective means to implement variability. By annotating code fragments with #ifdef and #endif directives, different program variants with or without these annotated fragments can be created, which can be used (among others) to implement software product lines. Although, such annotation-based approaches are frequently used in practice, researchers often criticize them for their negative effect on code quality and maintainability. In contrast to modularized implementations such as components or aspects, annotation-based implementations typically neglect separation of concerns, can entirely obfuscate the source code, and are prone to introduce subtle errors. Our goal is to rehabilitate annotation-based approaches by showing how tool support can address these problems. With views, we emulate modularity; with a visual representation of annotations, we reduce source code obfuscation and increase program comprehension; and with disciplined annotations and a product-line–aware type system, we prevent or detect syntax and type errors in the entire software product line. At the same time we emphasize unique benefits of annotations, including simplicity, expressiveness, and being language independent. All in all, we provide tool-based separation of concerns without necessarily dividing source code into physically separated modules; we name this approach virtual separation of concerns. We argue that with these improvements over contemporary preprocessors, virtual separation of concerns can compete with modularized implementation mechanisms. Despite our focus on annotation-based approaches, we do intend not give a definite answer on how to implement software product lines. Modular implementations and annotation-based implementations both have their advantages; we even present an integration and migration path between them. Our goal is to rehabilitate preprocessors and show that they are not a lost cause as many researchers think. On the contrary, we argue that – with the presented improvements – annotation-based approaches are a serious alternative for product-line implementation.

 
SCP 2010
S. Apel, C. Lengauer, B. Möller, and C. Kästner. An Algebraic Foundation for Automatic Feature-Based Program Synthesis. Science of Computer Programming (SCP), 75(11):1022--1047, November 2010. [ doi, .pdf, bib ]

Feature-Oriented Software Development (FOSD) provides a multitude of formalisms, methods, languages, and tools for building variable, customizable, and extensible software. Along different lines of research, different notions of a feature have been developed. Although these notions have similar goals, no common basis for evaluation, comparison, and integration exists. We present a feature algebra that captures the key ideas of feature orientation and provides a common ground for current and future research in this field, in which also alternative options can be explored. Furthermore, our algebraic framework is meant to serve as a basis for the upcoming development paradigms automatic feature-based program synthesis and architectural metaprogramming.

 
ASE 2010
S. Apel, C. Kästner, A. Größlinger, and C. Lengauer. Type Safety for Feature-Oriented Product Lines. Automated Software Engineering -- An International Journal (ASE), 17(3):251--300, 2010. [ http, .pdf, doi, bib ]

A feature-oriented product line is a family of programs that share a common set of features. A feature implements a stakeholder's requirement and represents a design decision or configuration option. When added to a program, a feature involves the introduction of new structures, such as classes and methods, and the refinement of existing ones, such as extending methods. A feature-oriented decomposition enables a generator to create an executable program by composing feature code solely on the basis of the feature selection of a user – no other information needed. A key challenge of product line engineering is to guarantee that only well-typed programs are generated. As the number of valid feature combinations grows combinatorially with the number of features, it is not feasible to type check all programs individually. The only feasible approach is to have a type system check the entire code base of the feature-oriented product line. We have developed such a type system on the basis of a formal model of a feature-oriented Java-like language. The type system guaranties type safety for feature-oriented product lines. That is, it ensures that every valid program of a well-typed product line is well-typed. Our formal model including type system is sound and complete.

 
ICSE 2010
J. Liebig, S. Apel, C. Lengauer, C. Kästner, and M. Schulze. An Analysis of the Variability in Forty Preprocessor-Based Software Product Lines. In Proceedings of the 32nd International Conference on Software Engineering (ICSE), pages 105--114, New York, NY: ACM Press, May 2010. Acceptance rate: 14 % (52/380). [ .pdf, acm, doi, bib ]

Over 30 years ago, the preprocessor cpp was developed to extend the programming language C by lightweight metaprogramming capabilities. Despite its error-proneness and low abstraction level, the cpp is still widely being used in presentday software projects to implement variable software. However, not much is known about how the cpp is employed to implement variability. To address this issue, we have analyzed forty open-source software projects written in C. Specifically, we answer the following questions: How does program size influence variability? How complex are extensions made via cpp's variability mechanisms? At which level of granularity are extensions applied? What is the general type of extensions? These questions revive earlier discussions on understanding and refactoring of the preprocessor. To answer them, we introduce several metrics measuring the variability, complexity, granularity, and type of extensions. Based on the data obtained, we suggest alternative implementation techniques. The data we have collected can influence other research areas, such as language design and tool support.

 
JOT 2009
C. Kästner, and S. Apel. Virtual Separation of Concerns -- A Second Chance for Preprocessors. Journal of Object Technology (JOT), 8(6):59--78, September 2009. Refereed Column. [ .pdf, http, bib ]

Conditional compilation with preprocessors like cpp is a simple but effective means to implement variability. By annotating code fragments with #ifdef and #endif directives, different program variants with or without these fragments can be created, which can be used (among others) to implement software product lines. Although, preprocessors are frequently used in practice, they are often criticized for their negative effect on code quality and maintainability. In contrast to modularized implementations, for example using components or aspects, preprocessors neglect separation of concerns, are prone to introduce subtle errors, can entirely obfuscate the source code, and limit reuse. Our aim is to rehabilitate the preprocessor by showing how simple tool support can address these problems and emulate some benefits of modularized implementations. At the same time we emphasize unique benefits of preprocessors, like simplicity and language independence. Although we do not have a definitive answer on how to implement variability, we want highlight opportunities to improve preprocessors and encourage research toward novel preprocessor-based approaches.

 
GPCE 2009
C. Kästner, S. Apel, and M. Kuhlemann. A Model of Refactoring Physically and Virtually Separated Features. In Proceedings of the 8th ACM International Conference on Generative Programming and Component Engineering (GPCE), pages 157--166, New York, NY: ACM Press, October 2009. Acceptance rate: 31 % (19/62). [ doi, acm, .pdf, bib ]

Physical separation with class refinements and method refinements à la AHEAD and virtual separation using annotations à la #ifdef or CIDE are two competing groups of implementation approaches for software product lines with complementary advantages. Although both groups have been mainly discussed in isolation, we strive for an integration to leverage the respective advantages. In this paper, we provide the basis for such an integration by providing a model that supports both, physical and virtual separation, and by describing refactorings in both directions. We prove the refactorings complete, such that every virtually separated product line can be automatically transformed into a physically separated one (replacing annotations by refinements) and vice versa. To demonstrate the feasibility of our approach, we have implemented the refactorings in our tool CIDE and conducted four case studies.

 
JOT 2009
S. Apel, and C. Kästner. An Overview of Feature-Oriented Software Development. Journal of Object Technology (JOT), 8(5):49--84, July/August 2009. Refereed Column. [ .pdf, http, bib ]

Feature-oriented software development (FOSD) is a paradigm for the construction, customization, and synthesis of large-scale software systems. In this survey, we give an overview and a personal perspective on the roots of FOSD, connections to other software development paradigms, and recent developments in this field. Our aim is to point to connections between different lines of research and to identify open issues.

 
SPLC 2009
C. Kästner, S. Apel, S. ur Rahman, M. Rosenmüller, D. Batory, and G. Saake. On the Impact of the Optional Feature Problem: Analysis and Case Studies. In Proceedings of the 13rd International Software Product Line Conference (SPLC), pages 181--190, Pittsburgh, PA: SEI, August 2009. Acceptance rate: 36 % (30/83). [ .pdf, bib ]

A software product-line is a family of related programs that are distinguished in terms of features. A feature implements a stakeholders' requirement. Different program variants specified by distinct feature selections are produced from a common code base. The optional feature problem describes a common mismatch between variability intended in the domain and dependencies in the implementation. When this occurs, some variants that are valid in the domain cannot be produced due to implementation issues. There are many different solutions to the optional feature problem, but they all suffer from drawbacks such as reduced variability, increased development effort, reduced efficiency, or reduced source code quality. In this paper, we examine the impact of the optional feature problem in two case studies in the domain of embedded database systems, and we survey different state-of-the-art solutions and their trade-offs. Our intension is to raise awareness of the problem, to guide developers in selecting an appropriate solution for their product-line project, and to identify opportunities for future research.

 
TOOLS EUROPE 2009
C. Kästner, S. Apel, S. Trujillo, M. Kuhlemann, and D. Batory. Guaranteeing Syntactic Correctness for all Product Line Variants: A Language-Independent Approach. In Proceedings of the 47th International Conference Objects, Models, Components, Patterns (TOOLS EUROPE), volume 33 of Lecture Notes in Business Information Processing, pages 175--194, Berlin/Heidelberg: Springer-Verlag, June 2009. Acceptance rate: 28 % (19/67). [ .pdf, http, doi, bib ]

A software product line (SPL) is a family of related program variants in a well-defined domain, generated from a set of features. A fundamental difference from classical application development is that engineers develop not a single program but a whole family with hundreds to millions of variants. This makes it infeasible to separately check every distinct variant for errors. Still engineers want guarantees on the entire SPL. A further challenge is that an SPL may contain artifacts in different languages (code, documentation, models, etc.) that should be checked. In this paper, we present CIDE, an SPL development tool that guarantees syntactic correctness for all variants of an SPL. We show how CIDE's underlying mechanism abstracts from textual representation and we generalize it to arbitrary languages. Furthermore, we automate the generation of safe plug-ins for additional languages from annotated grammars. To demonstrate the language-independent capabilities, we applied CIDE to a series of case studies with artifacts written in Java, C++, C, Haskell, ANTLR, HTML, and XML.

 
ICSE 2009
T. Thüm, D. Batory, and C. Kästner. Reasoning about Edits to Feature Models. In Proceedings of the 31st International Conference on Software Engineering (ICSE), pages 254--264, Los Alamitos, CA: IEEE Computer Society, May 2009. Acceptance rate: 12 % (50/405). [ .pdf, bib ]

Features express the variabilities and commonalities among programs in a software product line (SPL). A feature model defines the valid combinations of features, where each combination corresponds to a program in an SPL. SPLs and their feature models evolve over time. We classify the evolution of a feature model via modifications as refactorings, specializations, generalizations, or arbitrary edits. We present an algorithm to reason about feature model edits to help designers determine how the program membership of an SPL has changed. Our algorithm takes two feature models as input (before and after edit versions), where the set of features in both models are not necessarily the same, and it automatically computes the change classification. Our algorithm is able to give examples of added or deleted products and efficiently classifies edits to even large models that have thousands of features.

 
ICSE 2009
S. Apel, C. Kästner, and C. Lengauer. FeatureHouse: Language-Independent, Automated Software Composition. In Proceedings of the 31st International Conference on Software Engineering (ICSE), pages 221--231, Los Alamitos, CA: IEEE Computer Society, May 2009. Acceptance rate: 12 % (50/405). [ .pdf, bib ]

Superimposition is a composition technique that has been applied successfully in many areas of software development. Although superimposition is a general-purpose concept, it has been (re)invented and implemented individually for various kinds of software artifacts. We unify languages and tools that rely on superimposition by using the language-independent model of feature structure trees (FSTs). On the basis of the FST model, we propose a general approach to the composition of software artifacts written in different languages, Furthermore, we offer a supporting framework and tool chain, called FEATUREHOUSE. We use attribute grammars to automate the integration of additional languages, in particular, we have integrated Java, C#, C, Haskell, JavaCC, and XML. Several case studies demonstrate the practicality and scalability of our approach and reveal insights into the properties a language must have in order to be ready for superimposition.

 
ASE 2008
C. Kästner, and S. Apel. Type-checking Software Product Lines -- A Formal Approach. In Proceedings of the 23rd IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 258--267, Los Alamitos, CA: IEEE Computer Society, September 2008. Acceptance rate: 11 % (30/280). [ doi, .pdf, bib ]

A software product line (SPL) is an efficient means to generate a family of program variants for a domain from a single code base. However, because of the potentially high number of possible program variants, it is difficult to test all variants and ensure properties like type-safety for the entire SPL. While first steps to type-check an entire SPL have been taken, they are informal and incomplete. In this paper, we extend the Featherweight Java (FJ) calculus with feature annotations to be used for SPLs. By extending FJ's type system, we guarantee that – given a well-typed SPL – all possible program variants are welltyped as well. We show how results from this formalization reflect and help implementing our own language-independent SPL tool CIDE.

 
ICSE 2008
C. Kästner, S. Apel, and M. Kuhlemann. Granularity in Software Product Lines. In Proceedings of the 30th International Conference on Software Engineering (ICSE), pages 311--320, New York, NY: ACM Press, May 2008. Acceptance rate: 15 % (56/371). [ acm, .pdf, epub, doi, bib ]

Building software product lines (SPLs) with features is a challenging task. Many SPL implementations support features with coarse granularity - e.g., the ability to add and wrap entire methods. However, fine-grained extensions, like adding a statement in the middle of a method, either require intricate workarounds or obfuscate the base code with annotations. Though many SPLs can and have been implemented with the coarse granularity of existing approaches, fine-grained extensions are essential when extracting features from legacy applications. Furthermore, also some existing SPLs could benefit from fine-grained extensions to reduce code replication or improve readability. In this paper, we analyze the effects of feature granularity in SPLs and present a tool, called Colored IDE (CIDE), that allows features to implement coarse-grained and fine-grained extensions in a concise way. In two case studies, we show how CIDE simplifies SPL development compared to traditional approaches.

 
SPLC 2007
C. Kästner, S. Apel, and D. Batory. A Case Study Implementing Features Using AspectJ. In Proceedings of the 11st International Software Product Line Conference (SPLC), pages 223--232, Los Alamitos, CA: IEEE Computer Society, September 2007. Acceptance rate: 35 % (28/80). [ .pdf, bib ]

Software product lines aim to create highly configurable programs from a set of features. Common belief and recent studies suggest that aspects are well-suited for implementing features. We evaluate the suitability of AspectJ with respect to this task by a case study that refactors the embedded database system Berkeley DB into 38 features. Contrary to our initial expectations, the results were not encouraging. As the number of aspects in a feature grows, there is a noticeable decrease in code readability and maintainability. Most of the unique and powerful features of AspectJ were not needed. We document where AspectJ is unsuitable for implementing features of refactored legacy applications and explain why.

 
 

more...

Copyright Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

 
 
 

FOSD Cool Wall

The cool wall was created and evolved during the yearly FOSD student meetings (see fosd.net). With it, we would like to encourage researchers to look for better tool names. Up to 2012, the listing was completely subjective, feel free to complain. Starting 2013, we started voting and giving out a Coolest Tool Name award.

Cool Wall 2013
 
 
 

Private Interests

Juggling, Cooking, Board games, Concerts