TY - JOUR
AB - AbstractMany critical codebases are written in C, and most of them use preprocessor directives to encode variability, effectively encoding software product lines. These preprocessor directives, however, challenge any static code analysis. SPLlift, a previously presented approach for analyzing software product lines, is limited to Java programs that use a rather simple feature encoding and to analysis problems with a finite and ideally small domain. Other approaches that allow the analysis of real-world C software product lines use special-purpose analyses, preventing the reuse of existing analysis infrastructures and ignoring the progress made by the static analysis community. This work presents VarAlyzer, a novel static analysis approach for software product lines. VarAlyzer first transforms preprocessor constructs to plain C while preserving their variability and semantics. It then solves any given distributive analysis problem on transformed product lines in a variability-aware manner. VarAlyzer ’s analysis results are annotated with feature constraints that encode in which configurations each result holds. Our experiments with 95 compilation units of OpenSSL show that applying VarAlyzer enables one to conduct inter-procedural, flow-, field- and context-sensitive data-flow analyses on entire product lines for the first time, outperforming the product-based approach for highly-configurable systems.
AU - Schubert, Philipp
AU - Gazzillo, Paul
AU - Patterson, Zach
AU - Braha, Julian
AU - Schiebel, Fabian
AU - Hermann, Ben
AU - Wei, Shiyi
AU - Bodden, Eric
ID - 30511
IS - 1
JF - Automated Software Engineering
KW - inter-procedural static analysis
KW - software product lines
KW - preprocessor
KW - LLVM
KW - C/C++
SN - 0928-8910
TI - Static data-flow analysis for software product lines in C
VL - 29
ER -
TY - GEN
AB - We criticize some conceptual weaknesses in the recent literature on coalitional TUgames and propose, based on our critics, a new definition of dual TU-games that coincides with the one in the literature on the class of super-additive games. We justify our new definition in four alternative ways: 1. Via an adequate definition of ecient payo vectors. 2. Via a modification of the Bondareva-Shapley duality. 3. Via an explicit consideration of \coalition building". 4. Via associating general TU-games to coalition-production economies. Rather than imputations, we base our analysis on a modification of aspirations.
AU - Aslan, Fatma
AU - Duman, Papatya
AU - Trockel, Walter
ID - 15204
KW - TU-games
KW - duality
KW - core
KW - c-Core
KW - cohesive games
KW - complete game efficiency
TI - Duality for General TU-games Redefined
VL - 121
ER -
TY - CONF
AB - Routing is a challenging problem for wireless ad hoc networks, especially when the nodes are mobile and spread so widely that in most cases multiple hops are needed to route a message from one node to another. In fact, it is known that any online routing protocol has a poor performance in the worst case, in a sense that there is a distribution of nodes resulting in bad routing paths for that protocol, even if the nodes know their geographic positions and the geographic position of the destination of a message is known. The reason for that is that radio holes in the ad hoc network may require messages to take long detours in order to get to a destination, which are hard to find in an online fashion.
In this paper, we assume that the wireless ad hoc network can make limited use of long-range links provided by a global communication infrastructure like a cellular infrastructure or a satellite in order to compute an abstraction of the wireless ad hoc network that allows the messages to be sent along near-shortest paths in the ad hoc network. We present distributed algorithms that compute an abstraction of the ad hoc network in $\mathcal{O}\left(\log ^2 n\right)$ time using long-range links, which results in $c$-competitive routing paths between any two nodes of the ad hoc network for some constant $c$ if the convex hulls of the radio holes do not intersect. We also show that the storage needed for the abstraction just depends on the number and size of the radio holes in the wireless ad hoc network and is independent on the total number of nodes, and this information just has to be known to a few nodes for the routing to work.
AU - Jung, Daniel
AU - Kolb, Christina
AU - Scheideler, Christian
AU - Sundermeier, Jannik
ID - 4563
KW - greedy routing
KW - ad hoc networks
KW - convex hulls
KW - c-competitiveness
T2 - Proceedings of the 14th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS)
TI - Competitive Routing in Hybrid Communication Networks
ER -