While program comprehension tools often use static program analysis techniques to obtain useful information, they usually work only with sufficiently scalable techniques with limited precision. A possible improvement of this approach is to let the developer interactively reduce the scope of the code being analyzed and then apply a more precise analysis technique to the reduced scope. This paper presents a new version of the tool Slicito that allows developers to perform this kind of exploration on C\# code in Visual Studio. A common usage of Slicito is to use interprocedural data-flow analysis to identify the parts of the code most relevant for the given task and then apply symbolic execution to reason about the precise behavior of these parts. Inspired by Moldable Development, Slicito provides a set of program analysis and visualization building blocks that can be used to create specialized program comprehension tools directly in Visual Studio. We demonstrate the full scope of features on a real industrial example both in the text and in the following video: https://www.slicito.com/icpc2025video.mp4

Abstract Many verification tools currently rely on logic solvers as backend reasoning engines. Despite playing such a pivotal role, bugs are not uncommon in the complex codebases of these solvers. Validating their results is thus critical, with correctness witnesses often being used for this end. Output validation for constrained Horn clauses (CHC) solvers is not a well explored topic though, especially in regards to unsatisfiability results. This is a significant issue, given that CHC solvers are being increasingly employed in verification tooling. To address it, we propose an approach to validate CHC unsatisfiability results based on independently checkable proofs. Our approach is generic in regards to the solving algorithm, preprocessing steps, and exact proof format used, and works by first producing a coarse-grained proof during solving and then instantiating it into a suitable proof format by adding missing details, at which point the instantiated proof can be checked by an independent proof checker. We instrumented a state-of-the-art CHC solver to generate proofs in the Alethe format and performed a large-scale evaluation. Our results indicate that proofs can be produced with minimal overhead, can be efficiently checked, and have tractable sizes.

Although integrated development environments provide developers with code structure analysis tools, program comprehension tasks still require significant manual effort. A promising direction to solve this problem is Moldable Development, a way of programming which encourages developers to build custom program visualization tools during software development process. To foster this practice within the .NET development community, we provide a tool called SLICITO, capable of analyzing and visualizing a C# program structure in a highly configurable way. Since SLICITO is implemented as an extension to computational notebooks, it takes advantage of their interactivity and visualization principles used for data analysis, and applies them in the field of program comprehension. In contrast to similar tools for C#, SLICITO is more flexible and provides more detailed information in code inspection. Its usage is shown in a video located at https://www.slicito.com/icpc video.mp4.

Abstract The use of propositional logic and systems of linear inequalities over reals is a common means to model software for formal verification. Craig interpolants constitute a central building block in this setting for over-approximating reachable states, e.g. as candidates for inductive loop invariants. Interpolants for a linear system can be efficiently computed from a Simplex refutation by applying the Farkas’ lemma. However, these interpolants do not always suit the verification task—in the worst case, they can even prevent the verification algorithm from converging. This work introduces the decomposed interpolants, a fundamental extension of the Farkas interpolants, obtained by identifying and separating independent components from the interpolant structure, using methods from linear algebra. We also present an efficient polynomial algorithm to compute decomposed interpolants and analyse its properties. We experimentally show that the use of decomposed interpolants in model checking results in immediate convergence on instances where state-of-the-art approaches diverge. Moreover, since being based on the efficient Simplex method, the approach is very competitive in general.

Compiling dynamic languages to stack-based intermediate representations used in platforms such as. NET and Java proved to be useful, mainly due to the enhanced interoperability and security. To produce the best intermediate code possible, current approaches perform a detailed flow-sensitive type analysis of the original code and utilize its results to choose the most efficient operations of the target platform. As known from the traditional compilers, the standard way to further increase program performance is using a set of transformations, which increase its efficiency while preserving its semantics. However, these transformations are not directly usable in the compilers of dynamic languages, because these operate on a higher level of abstraction; moreover, dynamic languages pose specific challenges, such as those stemming from weak typing. In this paper we propose a set of transformations which fit into the architecture of a dynamic language compiler, fitting well together with the type analysis. For evaluation purposes, we implemented them to Peachpie, a compiler of PHP to. NET. Applying the transformations during compilation of WordPress resulted in improvement of 0.6 % in the generated assembly size, 1.8% in CPU time and 0.8% in memory consumption.

Abstract Smart system applications (SSAs)—a heterogeneous landscape of applications of Internet of things, cyber-physical systems, and smart sensing systems—are composed of autonomous yet inherently cooperating components. An important problem in this area is how to hoist the cooperation of software components forming dynamic groups—ensembles—at the architectural level of an SSA. This is hard since ensembles can overlap, be nested, and be dynamically formed and dismantled based on several criteria. A related problem is how to combine component and ensemble specification with a well-established language supported on multiple platforms. To target these problems, we propose a specification and implementation language Trait-based COmponent Ensemble Language (TCOEL) based on Scala internal DSL, to describe both the architecture and formation of dynamic ensembles of components and their functional internals. To raise the level of expressivity, we introduce the concept of domain-specific extensions (traits) to the TCOEL core to reflect different paradigms’ concerns—such as movement in a 2D map, state-space modeling of physical processes, and statistical reasoning about uncertainty. This allows for configuring TCOEL for the needs of a specific SSA use case and, at the same time, facilitates reuse. To evaluate TCOEL, we show how it can be beneficially used in addressing the coordination of agents in a RoboCup Rescue Simulation application.

Modern verification commonly models software with Boolean logic and a system of linear inequalities over reals and over-approximates the reachable states of the model with Craig interpolation to obtain, for example, candidates for inductive invariants. Interpolants for the linear system can be efficiently constructed from a Simplex refutation by applying the Farkas’ lemma. However, Farkas interpolants do not always suit the verification task and in the worst case they may even be the cause of divergence of the verification algorithm. This work introduces the decomposed interpolants, a fundamental extension of the Farkas interpolants obtained by identifying and separating independent components from the interpolant structure using methods from linear algebra. We integrate our approach to the model checker Sally and show experimentally that a portfolio of decomposed interpolants results in immediate convergence on instances where state-of-the-art approaches diverge. Being based on the efficient Simplex method, the approach is very competitive also outside these diverging cases.

Abstract During explicit software model checking, the tools spend a lot of time in state matching. This is implied not only by processing a huge number of states, but also by the fact that state representation is usually not small either. In this article, we present two dead variable analyses; applying them during the code-model-checking process results in size reduction of both state representation and explored state space itself. We implemented the analyses inside Java PathFinder and evaluate their impact in terms of memory and time reduction using several non-trivial benchmarks.

Smart Cyber-Physical Systems (sCPS) are complex distributed decentralized systems of cooperating components. They typically operate in uncertain environments and thus require means for managing variability at run-time. Architectural modes have traditionally been a proven means for the runtime variability. They are easy to understand, easy to realize in resource-constrained systems and (contrary to more sophisticated methods of learning) provide an explicit specification that can be inspected and validated at design time. However, in uncertain environments (which is the case of sCPS), they tend to lack expressivity to take into account the level of uncertainty and factor it in the mode-switching logic. In this paper we present a rich language to specify mode-switch guards. The semantics of the language is based on statistical tests, which, as we show, is a convenient way to reason about uncertainty in the state of the environment.

Dynamic languages, such as PHP and JavaScript, are widespread and heavily used. They provide dynamic features such as dynamic type system, virtual and dynamic method calls, dynamic includes, and built-in dynamic data structures. This makes it hard to create static analyses, e.g., for automatic error discovery. Yet exploiting errors in such programs, especially in web applications, can have significant impacts. In this paper, we present static analysis framework for PHP, automatically resolving features common to dynamic languages and thus reducing the complexity of defining new static analyses. In particular, the framework enables defining value and heap analyses for dynamic languages independently and composing them automatically and soundly. We used the framework to implement static taint analysis for finding security vulnerabilities. The analysis has revealed previously unknown security problems in real application. Comparing to existing state-of-the-art analysis tools for PHP, it has found more real problems with a lower false-positive rate.

Craig interpolants are widely used in program verification as a means of abstraction. In this paper, we (i) introduce Partial Variable Assignment Interpolants (PVAIs) as a generalization of Craig interpolants. A variable assignment focuses computed interpolants by restricting the set of clauses taken into account during interpolation. PVAIs can be for example employed in the context of DAG interpolation, in order to prevent unwanted out-of-scope variables to appear in interpolants. Furthermore, we (ii) present a way to compute PVAIs for propositional logic based on an extension of the Labeled Interpolation Systems, and (iii) analyze the strength of computed interpolants and prove the conditions under which they have the path interpolation property.

Abstract Component-based development is a well-established methodology of software development. Nevertheless, some of the benefits that the component based development offers are often neglected. One of them is modeling and subsequent analysis of component behavior, which can help establish correctness guarantees, such as absence of composition errors and safety of component updates. We believe that application of component behavior modeling in practice is limited due to huge differences between the behavior modeling languages (e.g., process algebras) and the common implementation languages (e.g., Java). As a result, many concepts of the implementation languages are either very different or completely missing in the behavior modeling languages. As an example, even though behavior modeling languages are practical for modeling and analysis of various message-based protocols, they are not well suited for modeling current component applications, where thread-based parallelism, lock-based synchronization, and nested method calls are the essential building blocks. With this in mind, we propose a new behavior modeling language for software components, Threaded Behavior Protocols (TBP). At the model level, TBP provides developers with the concepts known from the implementation languages and essential to most component applications. In addition, the theoretical framework of TBP provides a notion of correctness based on absence of communication errors and a refinement relation to verify correctness of hierarchical components. The main asset of TBP formalism is that it links together the notion of threads as used in imperative object oriented languages and the notion of refinement. For instance, this allows reasoning about hierarchical components composed of primitive components implemented in Java without the need of bridging abstractions and simplifications enforced by the modeling languages.

The more popular it is to build an application from reusable software components, the more desperate is the need for showing correctness of such a composition. This requires on one hand, being able to formally specify behavior of software components, while, on the other hand, providing appropriate tool support for verification of correctness of the composition. In this paper, we suggest use of the formalism of Extended Behavior Protocols and present a tool chain for verification of composition correctness of component applications. The advantage of the proposed approach is using a well-tested and supported model checker Spin as a backend. As a proof of the concept, we share our experience with application of the method.

Assuring components compatibility plays a crucial part in developing a reliable component system. Especially, when the components come from different vendors worldwide. In order to do so, an appropriate formalism for behavior specification of components is necessary. We propose a formalism of Threaded Behavior Protocols, which - unlike most other formalisms - allows for both analysis on the formal level (correctness and substitutability checking) and reasoning about conformance of a specification and the actual implementation. Moreover, the formalism is designed to be simple enough and to directly support constructs known from implementation languages (e.g., method calls, threads, synchronized blocks), so that it is easy to use by a nonprofessional.

Although there exist several software model checkers that check the code against properties specified e.g. via a temporal logic and assertions, or just verifying low-level properties (like unhandled exceptions), none of them supports checking of software components against a high-level behavior specification. We present our approach to model checking of software components implemented in Java against a high-level specification of their behavior defined via behavior protocols, which employs the Java PathFinder model checker and the protocol checker. The property checked by the Java PathFinder (JPF) tool (correctness of particular method call sequences) is validated via its cooperation with the protocol checker. We show that just the publisher/listener pattern claimed to be the key flexibility support of JPF (even though proved very useful for our purpose) was not enough to achieve this kind of checking