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 -