Abstract We present advances we brought to Mopsa for SV-Comp 2025. Most notably, Mopsa now supports bounded trace partitioning, constant widening with thresholds, and can check that all memory has been correctly deallocated. Further, Mopsa now integrates a sound support of bitfields. While Mopsa at SV-Comp previously relied on a fixed, homogeneous set of configurations to verify tasks, it can now automatically leverage semantic information from a previous analysis to trigger heuristic precision improvements in further analyses. With these improvements, Mopsa wins a silver medal in the SoftwareSystems category and ranks fifth in the NoOverflows category.

Abstract We present advances we brought to Mopsa for SV-Comp 2024. We significantly improved the precision of our verifier in the presence of dynamic memory allocation, library calls such as , -based loops, and integer abstractions. We introduced a witness validator for correctness witnesses. Thanks to these improvements, Mopsa won SV-Comp’sSoftwareSystemscategory by a large margin, scoring 2.5 times more points than the silver medalist, Bubaak-SpLit.

Abstract Mopsa is a multilanguage static analysis platform relying on abstract interpretation. It is able to analyze C, Python, and programs mixing these two languages; we focus on the C analysis here. It provides a novel way to combine abstract domains, in order to offer extensibility and cooperation between them, which is especially beneficial when relational numerical domains are used. The analyses are currently flow-sensitive and fully context-sensitive. We focus only on proving programs to be correct, as our analyses are designed to be sound and terminating but not complete. We present our first participation to SV-Comp, where Mopsa earned a bronze medal in the SoftwareSystems category.

Python is an increasingly popular dynamic programming language, particularly used in the scientific community and well-known for its powerful and permissive high-level syntax. Our work aims at detecting statically and automatically type errors. As these type errors are exceptions that can be caught later on, we precisely track all exceptions (raised or caught). We designed a static analysis by abstract interpretation able to infer the possible types of variables, taking into account the full control-flow. It handles both typing paradigms used in Python, nominal and structural, supports Python’s object model, introspection operators allowing dynamic type testing, dynamic attribute addition, as well as exception handling. We present a flow- and context-sensitive analysis with special domains to support containers (such as lists) and infer type equalities (allowing it to express parametric polymorphism). The analysis is soundly derived by abstract interpretation from a concrete semantics of Python developed by Fromherz et al. Our analysis is designed in a modular way as a set of domains abstracting a concrete collecting semantics. It has been implemented into the MOPSA analysis framework, and leverages external type annotations from the Typeshed project to support the vast standard library. We show that it scales to benchmarks a few thousand lines long, and preliminary results show it is able to analyze a small real-life command-line utility called PathPicker. Compared to previous work, it is sound, while it keeps similar efficiency and precision.

We present an abstract domain able to infer invariants on programs manipulating trees. Trees considered in the article are defined over a finite alphabet and can contain unbounded numeric values at their leaves. Our domain can infer the possible shapes of the tree values of each variable and find numeric relations between: the values at the leaves as well as the size and depth of the tree values of different variables. The abstract domain is described as a product of (1) a symbolic domain based on a tree automata representation and (2) a numerical domain lifted, for the occasion, to describe numerical maps with potentially infinite and heterogeneous definition set. In addition to abstract set operations and widening we define concrete and abstract transformers on these environments. We present possible applications, such as the ability to describe memory zones, or track symbolic equalities between program variables. We implemented our domain in a static analysis platform and present preliminary results analyzing a tree-manipulating toy-language.

Web applications use authentication mechanisms to provide user-friendly content to users. However, some dangerous techniques like session fixation attacks target these mechanisms, by making the legitimate user use a session identifier that is controlled by the attacker. In this way, he can then impersonate the legitimate user without the need to know his credentials. In this paper, we present SAWFIX, a PHP static analyzer that checks web applications for session fixation vulnerabilities. To the best of our knowledge, SAWFIX is the first analyzer that checks exhaustively for this type of vulnerabilities, while the other methods only ensure partial correctness that is limited to a fraction of possible executions. SAWFIX is based on abstract interpretation, which is a theory for approximating the semantics of programs and allows designing static analyzers that are fully automatic and sound by construction. We implemented a prototype of our approach and tested it on several complex web applications. We obtained promising results in terms of detection accuracy and processing time, which reflects the efficiency of our system.

Area-based localization is a simple and efficient approach, where each node estimates its position based on proximity information to some special nodes with known location, called anchors. Based on the anchors' coordinates, each node first determines its residence area and then approximates its position as the centroid of that area. Therefore, the accuracy of the estimated position depends on the size of the residence area; the smaller the residence area is, the better the accuracy is likely to be. Because the size of the residence area mainly depends on the number and the positions of anchor nodes, their deployment should be carefully considered in order to achieve a better accuracy while minimizing the cost. For this purpose, in this paper we conduct a theoretical study on anchor placement for a very popular area based localization approach. We determine the optimal anchor placement pattern for increased accuracy and how to achieve a particular accuracy goal with the least anchor count. Our analytical results are further validated through simulation.

Area-based localization algorithms use only the position of some reference nodes, called anchors, to estimate the residence area of the remaining nodes. Existing algorithms use a triangle, a ring or a circle as the geometric shape that defines the node's residence area. However, existing algorithms suffer from two major problems: (1) in some cases, they might make wrong decisions about a node presence inside a given area, or (2) they require high anchor density to achieve a low location estimation error and high ratio of localizable nodes. In this paper, we overcome these shortcomings by introducing a new approach for determining the node's residence area that is geometrically shaped as a half-symmetric lens. A novel half symmetric lens based localization algorithm (HSL) is proposed. HSL yields smaller residence areas, and consequently, better location accuracy than contemporary schemes. HSL further employs Voronoi diagram in order to boost the percentage of localizable nodes. The performance of HSL is validated through mathematical analysis, extensive simulations experiments and prototype implementation. The validation results confirm that HSL achieves better location accuracy and higher ratio of localizable nodes compared to competing algorithms.

In wireless sensor networks, in-network data aggregation filters out redundant sensor readings in order to reduce the energy and bandwidth consumed in disseminating the data to the base-station. In this paper, we investigate the problem of reliable collection of aggregated data with minimal latency. The aim is to form an aggregation tree such that there are k disjoint paths from each node to the base-station and find a collision-free schedule for node transmissions so that the aggregated data reaches the base-station in minimal time. We propose a novel algorithm for Reliable and Timely dissemination of Aggregated Data (RTAD). RTAD intertwines the formation of the aggregation tree and the allocation of time slots to nodes, and assigns parents to the individual nodes in order to maximize time slot reuse. The simulation results show that RTAD outperforms competing algorithms in the literature.

This paper focuses on data aggregation scheduling problem in wireless sensor networks (WSNs), to minimize time latency. Prior works on this problem have adopted a structured approach, in which a tree-based structure is used as an input for the scheduling algorithm. As the scheduling performance mainly depends on the supplied aggregation tree, such an approach cannot guarantee optimal performance. To address this problem, we propose approaches based on Semi-structured Topology (DAS-ST) and Unstructured Topology (DAS-UT). The approaches are based on two key design features, which are: (1) simultaneous execution of aggregation tree construction and scheduling, and (2) parent selection criteria that maximize the choices of parents for each node and maximize time slot reuse. We prove that the latency of DAS-ST is upper-bounded by ([2π/arccos(1/1+ϵ)]+4)R+Δ-4, where R is the network radius, Δ is the maximum node degree, and 0.05 <; ϵ ≤ 1. Simulations results show that DAS-UT outperforms DAS-ST and four competitive state-of-the-art aggregation scheduling algorithms in terms of latency and network lifetime.

The area-based localization algorithms use only the location information of some reference nodes, called anchors, to give the residence area of the remaining nodes. The current algorithms use triangle, ring or circle as a geometric shape to determine the sensors' residence area. Existing works suffer from two major problems: (1) in some cases, they might issue wrong decisions about nodes' presence inside a given area, or (2) they require high anchor density to achieve a low location estimation error. In this paper, we deal with the localization problem by introducing a new way to determine the sensors' residence area which shows a better accuracy than the existing algorithms. Our new localization algorithm, called HSL (Half Symmetric Lens based localization algorithm for WSN), is based on the geometric shape of half-symmetric lens. We also uses the Voronoi diagram in HSL to mitigate the problem of unlocalizable sensor nodes. Finally, we conduct extensive simulations to evaluate the performance of HSL. Simulation results show that HSL has better locatable ratio and location accuracy compared to representative state-of-the-art area-based algorithms.

In wireless sensor networks, reliability represents a design goal of a primary concern. To build a comprehensive reliable system, it is essential to consider node failures and intruder attacks as unavoidable phenomena. In this paper, we present a new intrusion-fault tolerant routing scheme offering a high level of reliability through a secure multi-path communication topology. Unlike existing intrusion-fault tolerant solutions, our protocol is based on a distributed and in-network verification scheme, which does not require any referring to the base station. Furthermore, it employs a new multi-path selection scheme seeking to enhance the tolerance of the network and conserve the energy of sensors. Extensive simulations with Tiny OS showed that our approach improves the overall Mean Time To Failure (MTTF) while conserving the energy resources of sensors.

Energy is a scarce resource in Wireless Sensor Networks. Some studies show that more than 70% of energy is consumed in data transmission. Since most of the time, the sensed information is redundant due to geographically collocated sensors, most of this energy can be saved through data aggregation. Furthermore, data aggregation improves bandwidth usage. Unfortunately, while aggregation eliminates redundancy, it makes data integrity verification more complicated since the received data is unique. In this paper, we present a new protocol that provides secure aggregation for wireless sensor networks. Our protocol is based on a two hops verification mechanism of data integrity. Our solution is essentially different from existing solutions in that it does not require referring to the base station for verifying and detecting faulty aggregated readings, thus providing a totally distributed scheme to guarantee data integrity. We carried out simulations using TinyOS environment. Simulation results show that the proposed protocol yields significant savings in energy consumption while preserving data integrity.