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 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
-
Information flow type systems enforce the security property of noninterference by detecting unauthorized data flows at compile-time. However, they require precise type annotations, making them difficult to use in practice as much of the legacy infrastructure is written in untyped or dynamically-typed languages. Gradual typing seamlessly integrates static and dynamic typing, providing the best of both approaches, and has been applied to information flow control, where information flow monitors are derived from gradual security types. Prior work on gradual information flow typing uncovered tensions between noninterference and the dynamic gradual guarantee- the property that less precise security type annotations in a program should not cause more runtime errors.This paper re-examines the connection between gradual information flow types and information flow monitors to identify the root cause of the tension between the gradual guarantees and noninterference. We develop runtime semantics for a simple imperative language with gradual information flow types that provides both noninterference and gradual guarantees. We leverage a proof technique developed for FlowML and reduce noninterference proofs to preservation proofs.more » « less
-
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
-
null (Ed.)Abstract Analyses of ancient food webs reveal important paleoecological processes and responses to a range of perturbations throughout Earth's history, such as climate change. These responses can inform our forecasts of future biotic responses to similar perturbations. However, previous analyses of ancient food webs rarely accounted for key differences between modern and ancient community data, particularly selective loss of soft-bodied taxa during fossilization. To consider how fossilization impacts inferences of ancient community structure, we (1) analyzed node-level attributes to identify correlations between ecological roles and fossilization potential and (2) applied selective information loss procedures to food web data for extant systems. We found that selective loss of soft-bodied organisms has predictable effects on the trophic structure of “artificially fossilized” food webs because these organisms occupy unique, consistent food web positions. Fossilized food webs misleadingly appear less stable (i.e., more prone to trophic cascades), with less predation and an overrepresentation of generalist consumers. We also found that ecological differences between soft- and hard-bodied taxa—indicated by distinct positions in modern food webs—are recorded in an early Eocene web, but not in Cambrian webs. This suggests that ecological differences between the groups have existed for ≥48 Myr. Our results indicate that accounting for soft-bodied taxa is vital for accurate depictions of ancient food webs. However, the consistency of information loss trends across the analyzed food webs means it is possible to predict how the selective loss of soft-bodied taxa affects food web metrics, which can permit better modeling of ancient communities.more » « less
