dataesr/scientific-paragraphs-categorization huggingface dataset:
When conducted, this work should probably rely on Maximum Likelihood optimization as in the ALE reconciliation software  (Szöllősi et al. 2012). For now, we believe that the use of "constraint-aware" reconciliations is preferable to current practices that consist in elaborating ad-hoc narratives once the reconciliations are obtained and compared with the character histories of the associates. Fig. 1 : Description of how geographical constraints are handled by the Mowgli software. Plain lines and nodes represent branches and nodes of the parasite tree, while cylindres and dashed ellipses represent branches and nodes of the host tree. The colours of a node correspond to geographical areas, these areas are observed (hence enforced) for extant taxa but inferred for ancestral nodes. A) The parasite tip u can be mapped to a tip x of the host tree if the areas of the host contain all areas of the parasite.
In this study, we identify the key message passing interface (MPI) operations required in atmospheric modelling; then, we use a skeleton program and a simulation framework (based on SST/macro simulation package) to simulate these MPI operations (transposition, halo exchange, and allreduce), with the perspective of future exascale machines in mind. The experimental results show that the choice of the collective algorithm has a great impact on the performance of communications; in particular, we find that the generalized ring-k algorithm for the alltoallv operation and the generalized recursive-k algorithm for the allreduce operation perform the best. In addition, we observe that the impacts of interconnect topologies and routing algorithms on the performance and scalability of transpositions, halo exchange, and allreduce operations are significant.
Y. Zheng and P. Marguinaud: Simulation of MPI communications on exascale supercomputers mance approaches to or is beyond 1 EFlops (1 EFlops = 10 3 PFlops), will become available  (Engelmann, 2014; Lagadapati et al. , 2016). Exascale HPC poses several challenges in terms of power consumption, performance, scalability, programmability, and resilience. The interconnect network of exascale HPC system becomes larger and more complex, and its performance which largely determines the overall performance of the HPC system is crucial to the performance of distributed applications. Designing energy-efficient costscalable interconnect networks and communication-efficient scalable distributed applications is an important component of HPC hardware/software co-design to address these challenges. Thus, evaluating and predicting the communication behaviour of distributed applications is obligatory; it is only feasible by modelling the communications and the underlying interconnect network, especially for the future supercomputer.
, 2009; Noeth et al. , 2009; Núñez et al. , 2010; Dechev and Ahn, 2013; Casanova et al. , 2015; Acun et al. , 2015; Jain et al. , 2016; Lagadapati et al. , 2016) ; however, is not very scalable because of the huge traces for numerous processes and limited extrapolation to future architecture  (Hoefler et al. , 2010; Núñez et al. , 2010). Online simulation has full scalability to future systems by running the skeleton program on top of simulators  (Zheng et al. , 2004; Janssen et al. , 2010; Engelmann, 2014; Degomme et al. , 2017) , but it has the challenge of developing a skeleton program from a complex distributed application. Most simulations in the aforementioned literature have demonstrated the scalability of simulators. The simulator xSim  (Engelmann, 2014 ) simulated a very simple message passing interface (MPI) program, which only calls MPI_Init and MPI_Finalize without any communication and computation, up to 2 27 processes.
SST/macro simulator Considering that the offline trace-driven simulation does not provide an easy way for extrapolating to future architectures, the online simulator SST/macro is selected here to model the communications of the atmospheric models for future exascale HPC systems. SST/macro is a coarse-grained parallel discrete event simulator which provides the best cost/accuracy trade-off simulation for large-scale distributed applications  (Janssen et al. , 2010). SST/macro is driven by either a trace file or a skeleton application. A skeleton application can be constructed from scratch or from an existing application manually or automatically by source-to-source translation tools. SST/macro intercepts the communications issued from the skeleton program to estimate their time rather than actually execute it by linking the skeleton application to the SST/macro library instead of the real MPI library.
Since the purpose of this study is to investigate the performance and scalability of communications in an atmospheric model, we construct the communication-only skeleton program from scratch by identifying the key MPI operations taking place in the atmospheric models. Congestion is a significant factor that affects the performance and scalability of MPI applications running on exascale HPC systems. SST/macro has three network models: the analytical model transfers the whole message over the network from point-to-point without packetizing and estimates the time delay t predominantly based on the logP approximation t = α + βN, ( 1 ) where α is the communication latency, β is the inverse bandwidth in second per byte, and N is the message size in bytes; the packet-level model PISCES (Packet-flow Interconnect Simulation for Congestion at Extreme Scale) divides the message into packets and transfers the packets individually; the flow-level model will be deprecated in the future.
Reduce the memory footprint and accelerate the simulation Although SST/macro is a parallel discrete event simulator that can reduce the memory footprint per node, its parallel efficiency degrades if more cores are used. Even with an MPI transposition of 10 5 processes, this all-to-all personalized communication has almost 10 10 discrete events, which consumes a considerable amount of memory and takes a very long time for simulation. Furthermore, almost every MPI program has a set-up step to allocate memory for storing the set-up information such as the parameters and the domain decomposition of all processes, which each process must know in order to properly communicate with other processes. Therefore, it needs to broadcast the parameters to and synchronize with all processes before actual communications and computation.
Even if the set-up information for a single process needs only 10 2 bytes of memory, a simulation of 10 5 processes MPI transposition will need 1 TB (10 2 × 10 5 × 10 5 = 10 12 bytes) of memory, which is not easily available on current computers if the simulator runs on a single node. In addition, the MPI operations in the set-up step are not only time-consuming but also affect subsequent communications. A common way to eliminate this effect is to iterate many times to obtain a robust estimation of communication time; however, one iteration is already very timeconsuming for simulation. To circumvent the issue of set-up steps, we use an external auxiliary program to create a shared memory segment on each node running SST/macro and initialize this memory with the set-up information of all the simulated MPI processes.
This work shows that the scalability of the spectral model is still acceptable in terms of MPI transposition. However, the wide halo exchange for the semi-Lagrangian method and the allreduce operation in the GCR iterative solver for the semi-implicit method, both of which are often adopted by the grid-point model, also face the stringent challenge of scalability at the exascale. In summary, both software (algorithms) and hardware (characteristics and configuration) are of great importance to the performance and scalability of the atmospheric model at the exascale. The software and hardware must be codesigned to address the challenge of the atmospheric model for exascale computing. As shown previously, the communications of the wide halo exchange for the semi-Lagrangian method and the allreduce operation in the GCR iterative solver for the semi-implicit method are expensive at the exascale.
Acknowledgements. This work was supported by the  ESCAPE (Energy-efficient Scalable Algorithms for Weather Prediction at Exascale ) project. The  ESCAPE  project has received funding from the  European Union 's  Horizon 2020 research and innovation programme  under grant agreement no. 671627. Our sincere gratitude goes to two anonymous reviewers and the topical editor  David Ham  for their thoughtful comments and suggestions that have helped improve this paper substantially. Edited by:  David Ham Reviewed  by: two anonymous referees.
Code availability. The code of the SST/macro simulator is publicly available at https://github. com/sstsimulator/sst-macro (Sandia National Laboratories, 2018). The skeleton programs, scripts, and our modified version of SST/macro 7. 1. 0 for the simulations presented in this paper are available at https://doi. org/10. 5281/zenodo. 1066934 (Zheng, 2017).
More precisely, a secure compilation chain must ensure that a dynamically compromised component cannot break the safety properties of the system at the target level any more than an arbitrary attackercontrolled component (with the same interface and privileges, but without undefined behaviors) already could at the source level. To illustrate the model, we construct a secure compilation chain for a small unsafe language with buffers, procedures, and components, targeting a simple abstract machine with built-in compartmentalization. We give a careful proof (mostly machine-checked in Coq) that this compiler satisfies our secure compilation criterion. Finally, we show that the protection guarantees offered by the compartmentalized abstract machine can be achieved at the machine-code level using either software fault isolation or a tagbased reference monitor.
INTRODUCTION Compartmentalization offers a strong, practical defense against a range of devastating low-level attacks, such as control-flow hijacks exploiting buffer overflows and other vulnerabilities in C, C++, and other unsafe languages  [18, 33, 81]. Widely deployed compartmentalization technologies include process-level privilege separation  [18, 33, 47]  (used in OpenSSH  [67]  and for sandboxing plugins and tabs in web browsers  [69] ), software fault isolation  [74, 79]  (e. g. , Google Native Client  [84] ), WebAssembly modules  [34]  in modern web browsers, and hardware enclaves (e. g. , Intel SGX  [38] ); many more are on the drawing boards  [14, 20, 71, 81]. These mechanisms offer an attractive base for building more secure compilation chains that mitigate low-level attacks  [30, 33, 44, 65, [75] [76] [77].
Such compromised components can only influence other components via controlled interactions respecting their interfaces and the other abstractions of the source language (e. g. , the stack discipline on calls and returns) Moreover, to model dynamic compromise and give each component full guarantees as long as it has not yet encountered undefined behavior, the temporal scope of compromise must also be restricted. In particular, compiler optimizations should never cause the effects of undefined behavior to show up before earlier "observable events" such as system calls. Unlike the spatial restriction, which requires some form of run-time enforcement in software or hardware, the temporal restriction can be enforced just by foregoing certain aggressive optimizations. For example, the temporal restriction (but not the spatial one) is already enforced by the CompCert C compiler  [56, 68] , providing a significantly cleaner model of undefined behavior than other C compilers  [68].
One particularly important advantage is that it allows us to reuse a whole-program compiler correctness result à la CompCert  [56]  as a black box, avoiding the need to prove any other simulations between the source and target languages. Our third contribution is a proof-of-concept secure compilation chain ( §4) for a simple unsafe sequential language featuring buffers, procedures, components, and a CompCert-like block-based memory model  [57]  ( §4. 1). Our entire compilation chain is implemented in the Coq proof assistant. The first step compiles our source language to a simple low-level abstract machine with built-in compartmentalization ( §4. 2). We use the proof technique from §3. 5 to construct careful proofs-many of them machine-checked in Coq-showing that this compiler satisfies RSCC ( §4.
(2) How can we effectively enforce secure compilation? Answer: Various mechanisms are possible; the simple compilation chain from §4 illustrates how either software fault isolation or tagged-based reference monitoring can enforce RSCC. (3) How can we achieve high assurance that the resulting compilation chain is indeed secure? Answer: We show that formal verification ( §4. 3) and property-based testing ( §4. 4) can be successfully used together for this in a proof assistant like Coq. We close with related ( §5) and future ( §6) work. The appendix presents omitted details. Our Coq development is available at https: //github. com/secure-compilation/when-good-components-go-bad/.
To illustrate, consider the partial program P defined below. According to RSC DC there exists a source-level context C S (for instance the one above) that explains the prefix m in terms of the source language in one of two ways: either C S [P] can do the entire m in the source, or C S [P] encounters an undefined behavior in P after a prefix of m, for instance the following one: t ′ = [ E. read ( ) ; Ret ( " feedbeef " ) ; P. foo ( " feedbeef " ) ; Undef ( P ) ] As in CompCert  [56, 68] , we treat undefined behaviors as observable events at the end of the execution trace, allowing compiler optimizations that move an undefined behavior to an earlier point in the execution, but not past any other observable event. While some other C compilers would need to be adapted to respect this discipline  [68] , limiting the temporal scope of undefined behavior is a necessary prerequisite for achieving security against dynamic compromise.
Moreover, if trace events are coarse enough (e. g. , system calls and cross-component calls) we expect this restriction to have a negligible performance impact in practice. One of the top-level CompCert theorems does, in fact, already capture dynamic compromise in a similar way to RSC DC. Using our notations this CompCert theorem looks as follows: ∀P t. (P↓)⇝t ⇒ ∃t ′. P⇝t ′ ∧ (t ′ =t ∨ t ′ ≺t) This says that if a compiled whole program P↓ can produce a trace t with respect to the target semantics, then in the source P can produce either the same trace or a prefix of t followed by undefined behavior. In particular this theorem does provide guarantees to undefined programs up to the point at which they encounter undefined behavior. The key difference compared to our secure compilation chains is that CompCert does not restrict undefined behavior spatially: in CompCert undefined behavior breaks all security guarantees of the whole program, while in our work we restrict undefined behavior to the component that causes it.
A Generic Proof Technique for RSCC We now describe an effective and general proof technique for RSCC. First, we observe that the slightly simpler RSC DC MD implies RSCC. Then we provide a generic proof in Coq that any compilation chain obeys RSC DC MD if it satisfies certain well-specified assumptions on the source and target languages and the compilation chain. Our proof technique yields simpler and more scalable proofs than previous work in this space  [43]. In particular, it allows us to directly reuse a compiler correctness result à la CompCert, which supports separate compilation but only guarantees correctness for whole programs  [45] ; which avoids proving any other simulations between the source and target languages. Achieving this introduces some slight complications in the proof structure, but it nicely separates the correctness and security proofs and allows us to more easily tap into the CompCert infrastructure.
Because our source language is unsafe, however, t need not be an extension of m: it can end earlier with an undefined behavior ( §3. 2). So the final step in our proof shows that if the source execution ends earlier with an undefined behavior (t ′ ≺m), then this undefined behavior can only be caused by P (i. e. , t ′ ≺ P m), not by C S , which was correctly generated by our back-translation (Assumption 7). MD proof The generic RSC DC MD proof outlined above relies on assumptions about the compartmentalizing compilation chain. In the reminder of this subsection we give details about these assumptions, while still trying to stay high level by omitting some of the low-level details in our Coq formalization. (C T ∪ P↓)⇝ * m (C S ↓ ∪ P ′ ↓)⇝ * m (m, I C ∪ I P )↑ = (C S ∪ P ′ )⇝ * m C S ↓ ⇝ * I P m P↓ ⇝ * I C m (C S ↓ ∪P↓)⇝ * m m ≤ t ∨ t ≺ P m (C S ∪ P) ⇝ t ∧ (m ≤ t ∨ t ≺ m) The first assumption we used in the proof above is that every trace prefix that a target program can produce can also be produced by a source program with the same interface.
Thus we can only assume we can back-translate prefixes that are produced by the target semantics. As further discussed in §5, similar back-translation techniques that start from finite execution prefixes have been used to prove fully abstract compilation  [41, 64]  and very recently RSC  [66]  and even stronger variants  [6]. Our back-translation, on the other hand, produces not just a source context, but a whole program. In the top-left corner of Figure  4 , we assume that this resulting program, (m, I C ∪ I P )↑, can be partitioned into a context C S that satisfies the interface I C , and a program P ′ that satisfies I P. Our second assumption is a form of forward compiler correctness for unsafe languages and a direct consequence of a forward simulation proof in the style of CompCert  [56].
SECURE COMPILATION CHAIN We designed a simple proof-of-concept compilation chain to illustrate the RSCC property. The compilation chain is implemented in Coq. The source language is a simple, unsafe imperative language with buffers, procedures, and components ( §4. 1). It is first compiled to an intermediate compartmentalized machine featuring a compartmentalized, block-structured memory, a protected call stack, and a RISC-like instruction set augmented with an Alloc instruction for dynamic storage allocation plus cross-component Call and Return instructions ( §4. 2). We can then choose one of two back ends, which use different techniques to enforce the abstractions of the compartmentalized machine against realistic machine-codelevel attackers, protecting the integrity of component memories and enforcing interfaces and cross-component call/return discipline.
Values include integers, pointers, and an undefined value ⊤, which is obtained when reading from an uninitialized piece of memory or as the result of an erroneous pointer operation. As in CompCert and LLVM  [55] , our semantics propagates these ⊤ values and yields an undefined behavior if a ⊤ value is ever inspected. (The C standard, by contrast, specifies that a program is undefined as soon as an uninitialized read or bad pointer operation takes place. ) Memory Model The memory model for both source and compartmentalized machine is a slightly simplified version of the one used in CompCert  [57]. Each component has an infinite memory composed of finite blocks, each an array of values. Accordingly, a pointer is a triple (C, b, o), where C is the identifier of the component that owns the block, b is a unique block identifier, and o is an offset inside the block.
Arithmetic operations on pointers are limited to testing equality, testing ordering (of pointers into the same block), and changing offsets. Pointers cannot be cast to or from integers. Dereferencing an integer yields undefined behavior. For now, components are not allowed to exchange pointers; as a result, well-defined components cannot access each others' memories at all. We hope to lift this restriction in the near future. This abstract memory model is shared by the compartmentalized machine and is mapped to a more realistic flat address space by the back ends. Events Following CompCert, we use a labeled operational semantics whose events include all interactions of the program with the external world (e. g. , system calls), plus events tracking control transfers from one component to another.
RSCC Proof in Coq We have proved that a compilation chain targeting the compartmentalized machine satisfies RSCC, applying the technique from §3. 5. As explained in §2, the responsibility for enforcing secure compilation can be divided among the different parts of the compilation chain. In this case, it is the target machine of §4. 2 that enforces compartmentalization, while the compiler itself is simple, standard, and not particularly interesting (so omitted here). For showing RSC DC MD , all the assumptions from §3. 5 are proved using simulations. Most of this proof is formalized in Coq: the only non-trivial missing pieces are compiler correctness (Assumptions 2 and 6) and composition (Assumption 5). The first is standard and essentially orthogonal to secure compilation; eventually, we hope to scale the source language up to a compartmentalized variant of C and reuse CompCert's mechanized correctness proof.
A mechanized proof of composition is underway. Despite these missing pieces, our formalization is more detailed than previous paper proofs in the area  [3, 5, 9-11, 29, 40, 41, 43, 61, 63-65]. Indeed, we are aware of only one fully mechanized proof about secure compilation: Devriese et al. 's  [24]  recent full abstraction result for a translation from the simply typed to the untyped λ-calculus in around 11KLOC of Coq. Our Coq development comprises around 22KLOC, with proofs taking about 60%. Much of the code is devoted to generic models for components, traces, memory, and undefined behavior that we expect to be useful in proofs for more complex languages and compilers, such as CompCert. We discuss some of the most interesting aspects of the proof below. Back-translation function. We proved Assumption 1 by defining a↑ function that takes a finite trace prefix m and a program interface I and returns a whole source program that respects I and produces m.
Each generated component uses the local variable local[0] to track how many events it has emitted. When a procedure is invoked, it increments local[0] and produces the event in m whose position is given by the counter's value. For this back-translation to work correctly, m is restricted to look like a trace emitted by a real compiled program with an I interface-in particular, every return in the trace must match a previous call. This back-translation is illustrated in Figure  8  on a trace of four events. The generated program starts running MainC. mainP, with all counters set to 0, so after testing the value of MainC. local[0], the program runs the first branch of mainP: local [ 0 ] + + ; C. p ( 0 ) ; MainC. mainP ( 0 ) ; After bumping local[0], mainP emits its first event in the trace: the call C.
p(0). When that procedure starts running, C's counter is still set to 0, so it executes the first branch of procedure p: local [ 0 ] + + ; return 1 ; The return is C's first event in the trace, and the second of the program. When mainP regains control, it calls itself recursively to emit the other events in the trace (we can use tail recursion to iterate in the standard way, since internal calls are silent events). The program continues executing in this fashion until it has emitted all events in the trace, at which point it terminates execution. Partial semantics. Our partial semantics has a simple generic definition based on the small-step operational semantics of a whole target program, which we denote as α -→. In this semantics, each step is labeled with an action α that is either an event or a silent action τ.