Applying model-based software analysis to eliminate cyclic build dependencies

What if you want to migrate to a modern build system, but the software you have been developing for the past years has cyclic build dependencies (Figure 1) which are no longer supported by the new build system? Simply identify the cycles in the build configuration and resolve the identified cycles, right?

Figure 1: Illustrative example of a cyclic build dependency

Turns out it that in most cases it’s far from trivial to resolve a cyclic build dependency:

1. When manually analyzing the root cause of a cyclic dependency, the number of makefile targets and their interdependencies could simply be too large for a software developer to comprehend and identify all (direct and indirect) cycles (see Figure 2).
2. Finding the root cause of identified cycles at the source code level requires navigating back and forth between makefiles and symbols within source code modules. This is extremely time consuming and difficult to get complete, as there can be many source code level dependencies to find and evaluate. And there’s no easy strategy to filter out the suspicious dependencies that might have been introduced unwittingly.?
3. Breaking a cycle without introducing new ones requires a deep understanding of surrounding source code level dependencies. Due to the level of indirections and the many source level dependencies, it’s hard to come up with a redesign that effectively breaks the cycle without introducing new ones.

Figure 2: Industrial case, showing 28 makefile targets that form ~30 direct- and indirect cycles

Due to above problems, it takes an average senior software developer multiple days to analyze a single cyclic build dependency. As the software under development consists of several hundred cyclic build dependencies, only the analysis of the cyclic build dependencies already takes man years of work. How can this be accelerated to keep the transition to the new build system economically feasible?

After executing the analysis a few times manually and gaining sufficient understanding of the problem, we chose to address this problem with ESI’s Renaissance [1]; a tool supported method for model-based software analysis. This semi-automated method helps to quickly answer analysis questions of engineers and architects, preventing manual error-prone work and improving efficiency. As depicted in Figure 3, Renaissance offers a framework, amongst others, to:

1. Scan a software archive and extract a software model from artefacts of interest
2. Merge partial software models extracted from found artefacts into a consolidated knowledge base
3. Store the knowledge base in a graph database (e.g. Neo4j) for exploratory purposes and rapid prototyping of queries to extract the needed data
4. Generate visualizations to visualize the data of interest as queried from the knowledge base

Figure 3: Model-based software analysis with Renaissance

Renaissance in fact is a framework, designed to be extended and tailored to solve domain specific use cases beyond the capabilities of COTS tools. The framework offers a base implementation to extract dependency- and call graphs from a limited set of supported code artefact types, of which C/C++ is one of them. In addition, the framework offers a base implementation to generate visualizations of nodes and edges to represent software structures as queried from the knowledge database in a GraphML format, which can be opened by tools like YEd.

To solve our industrial case, we have extended the framework with an extractor to extract dependency graphs from makefiles described with a customer specific makefile syntax, to realize the mapping from makefile targets to source code modules and the dependencies between makefile targets. Next, we were able to rapidly develop the query to retrieve all makefile targets and their specified source code modules that form cyclic build dependencies. Finally, we were able to generate two types of visualizations:

1. Overview showing all (and only the) makefile targets and their interdependencies that form cyclic build dependencies. Suspicious interdependencies are colored red (very likely to be an undesired dependency) or orange (could be an undesired dependency, based on heuristics) and serve as a starting point for further analysis.
2. Per cycle, a graph showing exactly the makefile targets (2 or more) that form the cyclic build dependency to analyze in detail. As illustrated in Figure 4, the graph represents makefile targets, source modules, header files, function declarations and function definitions and their interrelationships like implements and calls that form the cycle.?

Figure 4: Illustrative example of a cyclic build dependency, expanded to the code level symbols.

After having developed this proof of concept, we were able to reproduce an analysis on a software component with many cycles from weeks to minutes, with very positive responses from both internal and external project stakeholders. Next step for us is to shield the complexity of the solution from the software developers (e.g. with command-line interfaces) so that it can be used in practice to combat cyclic build dependencies.

Key take aways:

• Organizing for structural and continuous improvement, with the rightly skilled and motivated experts and leveraging state-of-the-art methods and tools provided by our partners like ESI, hugely outperforms what’s possible with conventional methods, tools and organizational structures.
• Renaissance as a method and framework really shines to address use cases similar as described in this article. And we have in this article not even scratched the surface of what's possible with Renaissance, for example to leverage it's code refactoring capabilities. Without a doubt a powerful addition to the portfolio of an automation expert!

I hope you have enjoyed this article and would love it when you leave your comments in case you’d want to know more or want to share constructive feedback.

Best regards,

Niels Brouwers.

Credits:

Paul Nelissen (Capgemini), Arjan Mooij (TNO-ESI), Cerion Armour-Brown (Capgemini), Jos Hegge (TNO-ESI), Jeroen Kersten (Capgemini) and René van Kempen (Capgemini)

References:

[1] Model-based software analysis, ESI: https://esi.nl/research/output/methods/model-based-software-analysis