Abstract. D-Finder 2 is a new tool for deadlock detection in concurrent systems based on effective invariant computation to approximate the effects of interactions among modules. It is part of the BIP framework, which provides various tools centered on a component-based language for incremental design. The presented tool shares its theoretical roots with a previous implementation, but was completely rewritten to take advantage of a new version of BIP and various new results on the theory of invariant computation. The improvements are demonstrated by comparison with previous work and reports on new results on a practical case study. Language. D-Finder 2 is part of a framework of tools that share a common language, BIP, to describe component-based systems [1] . The language is based on atomic components and connectors to describe their interactions. Components can also be hierarchically organized to build new components. An atomic component is a transition system B = (L, P, T ), where L = {l 1 , l 2 , . . . , l k } is a set of control locations, P is a set of ports, and T ⊆ L × P × L is a set of transitions. A component additionally can contain data and use C code for actions and conditions on the transitions to manipulate this data. Figure 1 shows a graphical representation of two atomic components B 1 and B 2 . We use cycles for locations and arrows for transitions. Every transition is labeled by a port to synchronize with ports of other components to create interactions. In the example, the ports trigger and tick of the two components are synchronized, which means the corresponding transitions have to be executed concurrently, and are only available if the guards in both components are fulfilled. The transition rel can be taken whenever a component is in the fire location. We can give only a very brief description of BIP here, please refer to [1] for more details.  The rule states that if all components B i fulfill their respective component in- with the interactions γ fulfills an interaction invariant Ψ , and if furthermore the conjunction of the invariants ( i Φ i ) ∧ Ψ implies a predicate on the global system Φ, then also the global system γ {B i } i itself fulfills Φ. In this paper we concentrate on global deadlock-freedom. Indeed, it suffices to prove the invariance of the predicate ¬DIS, where DIS is the set of states of the system from which all the interactions are disabled. Tool Chain. The design flow between BIP and D-Finder is sketched in Figure 2 . The framework allows to (1) start from scratch and describe a composite system with the BIP language, or (2) to use the Language Factory to translate existing models described in languages such as C, DOL [15]
We compared our implementation LDFC-BIP to D-Finder 2 REF .
D-Finder 2: Towards Efficient Correctness of Incremental Design
NASA Formal Methods
Computer Science