An official website of the United States government
Indirect calls, while facilitating dynamic execution characteristics in C and C++ programs, impose challenges on precise construction of the control-flow graphs (CFG). This hinders effective program analyses for bug detection (e.g., fuzzing) and program protection (e.g., control-flow integrity). Solutions using data-tracking and type-based analysis are proposed for identifying indirect call targets, but are either time-consuming or imprecise for obtaining the analysis results. Multi-layer type analysis (MLTA), as the state-of-the-art approach, upgrades type-based analysis by leveraging multi-layer type hierarchy, but their solution to dealing with the information flow between multi-layer types introduces false positives. In this paper, we propose strong multi-layer type analysis (SMLTA) and implement the prototype, DEEPTYPE, to further refine indirect call targets. It adopts a robust solution to record and retrieve type information, avoiding information loss and enhancing accuracy. We evaluate DEEPTYPE on Linux kernel, 5 web servers, and 14 user applications. Compared to TypeDive, the prototype of MLTA, DEEPTYPE is able to narrow down the scope of indirect call targets by 43.11% on average across most benchmarks and reduce runtime overhead by 5.45% to 72.95%, which demonstrates the effectiveness, efficiency and applicability of SMLTA.
more »
« less
This content will become publicly available on June 10, 2026
Webs and Flow-Directed Well-Typedness Preserving Program Transformations
We definewebsto be the collections of producers and consumers (e.g., functions and calls) in a program that are constrained: in higher-order languages, multiple functions can flow to the same call, all of which must agree on an interface (e.g., calling convention). We argue that webs are fundamentally theunit of transformation: a change to one member requires changes across the entire web. We introduce a web-centric intermediate language that exposes webs as annotations, and describe web-based (that is, flow-directed) transformations guided by these annotations. As they affect all members of a web, these transformations are interprocedural, operating over entire modules. Through the lens of webs we reframe and generalize a collection of transformations from the literature, including dead-parameter elimination, uncurrying, and defunctionalization, as well as describe novel transformations. We contrast this approach with rewriting strategies that rely on inlining and cascading rewrites. Webs are an over-approximation of the semantic function-call relationship produced by control-flow analyses (CFA). This information is inherently independent from the transformations; more precise analyses permit more transformations. A limitation of precise analyses is that the transformations may not maintain well-typedness, as the type system is a less-precise static analysis. Our solution is a simple and lightweight typed-based analysis that causes the flow-directed transformations to preserve well-typedness, making flow-directed, type-preserving transformations easily accessible in many compilers. This analysis builds on unification, distinguishing types thatlookthe same from types that have tobethe same. Our experiments show that while our analysis is theoretically less precise, in practice its precision is similar to CFAs.
more »
« less
- Award ID(s):
- 2212538
- PAR ID:
- 10607946
- Publisher / Repository:
- Association for Computing Machinery
- Date Published:
- Journal Name:
- Proceedings of the ACM on Programming Languages
- Volume:
- 9
- Issue:
- PLDI
- ISSN:
- 2475-1421
- Page Range / eLocation ID:
- 177:1-177:25
- Subject(s) / Keyword(s):
- Compilers Functional languages Automated static analysis Flow Analysis Program Transformations Type Systems
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Food webs are complex ecological networks that reveal species interactions and energy flow in ecosystems. Prevailing ecological knowledge on forested streams suggests that their food webs are based on allochthonous carbon, driven by a constant supply of organic matter from adjacent vegetation and limited primary production due to low light conditions. Extreme climatic disturbances can disrupt these natural ecosystem dynamics by altering resource availability, which leads to changes in food web structure and functioning. Here, we quantify the response of stream food webs to two major hurricanes (Irma and María, Category 5 and 4, respectively) that struck Puerto Rico in September 2017. Within two tropical forested streams (first and second order), we collected ecosystem and food web data 6 months prior to the hurricanes and 2, 9, and 18 months afterward. We assessed the structural (e.g., canopy) and hydrological (e.g., discharge) characteristics of the ecosystem and monitored changes in basal resources (i.e., algae, biofilm, and leaf litter), consumers (e.g., aquatic invertebrates, riparian consumers), and applied Layman's community‐wide metrics using the isotopic composition of13C and15N. Continuous stream discharge measurements indicated that the hurricanes did not cause an extreme hydrological event. However, the sixfold increase in canopy openness and associated changes in litter input appeared to trigger an increase in primary production. These food webs were primarily based on terrestrially derived carbon before the hurricanes, but most taxa (includingAtyaandXiphocarisshrimp, the consumers with highest biomass) shifted their food source to autochthonous carbon within 2 months of the hurricanes. We also found evidence that the hurricanes dramatically altered the structure of the food web, resulting in shorter (i.e., smaller food‐chain length), narrower (i.e., lower diversity of carbon sources) food webs, as well as increased trophic species packing. This study demonstrates how hurricane disturbance can alter stream food webs, changing the trophic base from allochthonous to autochthonous resources via changes in the physical environment (i.e., canopy defoliation). As hurricanes become more frequent and severe due to climate change, our findings greatly contribute to our understanding of the mechanisms that maintain forested stream trophic interactions amidst global change.more » « less
-
Abstract AimHow do factors such as space, time, climate and other ecological drivers influence food web structure and dynamics? Collections of well‐studied food webs and replicate food webs from the same system that span biogeographical and ecological gradients now enable detailed, quantitative investigation of such questions and help integrate food web ecology and macroecology. Here, we integrate macroecology and food web ecology by focusing on how ecogeographical rules [the latitudinal diversity gradient (LDG), Bergmann's rule, the island rule and Rapoport's rule] are associated with the architecture of food webs. LocationGlobal. Time periodCurrent. Major taxa studiedAll taxa. MethodsWe discuss the implications of each ecogeographical rule for food webs, present predictions for how food web structure will vary with each rule, assess empirical support where available, and discuss how food webs may influence ecogeographical rules. Finally, we recommend systems and approaches for further advancing this research agenda. ResultsWe derived testable predictions for some ecogeographical rules (e.g. LDG, Rapoport's rule), while for others (e.g., Bergmann's and island rules) it is less clear how we would expect food webs to change over macroecological scales. Based on the LDG, we found weak support for both positive and negative relationships between food chain length and latitude and for increased generality and linkage density at higher latitudes. Based on Rapoport's rule, we found support for the prediction that species turnover in food webs is inversely related to latitude. Main conclusionsThe macroecology of food webs goes beyond traditional approaches to biodiversity at macroecological scales by focusing on trophic interactions among species. The collection of food web data for different types of ecosystems across biogeographical gradients is key to advance this research agenda. Further, considering food web interactions as a selection pressure that drives or disrupts ecogeographical rules has the potential to address both mechanisms of and deviations from these macroecological relationships. For these reasons, further integration of macroecology and food webs will help ecologists better understand the assembly, maintenance and change of ecosystems across space and time.more » « less
-
Abstract We study webs of 5-branes with 7-branes in Type IIB string theory from a geometric perspective. Mathematically, a web of 5-branes with 7-branes is a tropical curve in$$\mathbb {R}^2$$ with focus-focus singularities introduced. To any such a webW, we attach a log Calabi–Yau surface (Y, D) with a line bundleL. We then describe supersymmetric webs, which are webs defining 5d superconformal field theories (SCFTs), in terms of the geometry of (Y, D, L). We also introduce particular supersymmetric webs called “consistent webs, and show that any 5d SCFT defined by a supersymmetric web can be obtained from a consistent web by adding free hypermultiplets. Using birational geometry of degenerations of log Calabi–Yau surfaces, we provide an algorithm to test the consistency of a web in terms of its dual polygon. Moreover, for a consistent webW, we provide an algebro-geometric construction of the mirror$$\mathcal {X}^{\textrm{can}}$$ to (Y, D, L), as a non-toric canonical 3-fold singularity, and show that M-theory on$$\mathcal {X}^{\textrm{can}}$$ engineers the same 5d SCFT asW. We also explain how to derive explicit equations for$$\mathcal {X}^{\textrm{can}}$$ using scattering diagrams, encoding disk worldsheet instantons in the A-model, or equivalently the BPS states of an auxiliary rank one 4d$$\mathcal {N}=2$$ theory.more » « less
-
Abstract Webs are planar graphs with boundary that describe morphisms in a diagrammatic representation category for $$\mathfrak{sl}_k$$. They are studied extensively by knot theorists because braiding maps provide a categorical way to express link diagrams in terms of webs, producing quantum invariants like the well-known Jones polynomial. One important question in representation theory is to identify the relationships between different bases; coefficients in the change-of-basis matrix often describe combinatorial, algebraic, or geometric quantities (e.g., Kazhdan–Lusztig polynomials). By ”flattening” the braiding maps, webs can also be viewed as the basis elements of a symmetric group representation. In this paper, we define two new combinatorial structures for webs: band diagrams and their one-dimensional projections, shadows, which measure depths of regions inside the web. As an application, we resolve an open conjecture that the change of basis between the so-called Specht basis and web basis of this symmetric group representation is unitriangular for $$\mathfrak{sl}_3$$-webs ([ 33] and [ 29].) We do this using band diagrams and shadows to construct a new partial order on webs that is a refinement of the usual partial order. In fact, we prove that for $$\mathfrak{sl}_2$$-webs, our new partial order coincides with the tableau partial order on webs studied by the authors and others [ 12, 17, 29, 33]. We also prove that though the new partial order for $$\mathfrak{sl}_3$$-webs is a refinement of the previously studied tableau order, the two partial orders do not agree for $$\mathfrak{sl}_3$$.more » « less
