dataesr/scientific-paragraphs-categorization huggingface dataset:
6 and 0. 8, this means that the connectivity of each subgraphs induced in each partition remains close from that of the original graph. In addition, our heuristic is the first to propose partitions whose vertices induced in each partition are strongly connected. DPHV is able to partition large-scale graphs in a parallel and distributed architecture, all while preserving the graph topology as much as possible. While optimizing the number of cutedges in order to minimize the communication costs. In addition DPHV is scalable and supports the large-scale graph. We compare our approach with others parallel and distributed algorithms: DFEP  [15] , JA-BE-JA  [24]  and Greedy  [13]. Figure  16  shows the experimental results of graph algorithms on the datasets. In terms of velocity, Greedy  [13]  and DFED  [15]  outperform the performance of our algorithm.
We describe a technique for systematic testing of multithreaded programs. We combine Quasi-Optimal Partial-Order Reduction, a state-of-the-art technique that tackles path explosion due to interleaving non-determinism, with symbolic execution to handle data non-determinism. Our technique iteratively and exhaustively finds all executions of the program. It represents program executions using partial orders and finds the next execution using an underlying unfolding semantics. We avoid the exploration of redundant program traces using cutoff events. We implemented our technique as an extension of KLEE and evaluated it on a set of large multi-threaded C programs. Our experiments found several previously undiscovered bugs and undefined behaviors in memcached and GNU sort, showing that the new method is capable of finding bugs in industrial-size benchmarks.
Data non-determinism in sequential and concurrent programs, and scheduling non-determinism are two major sources of path explosion in program analysis. Symbolic execution  [30, 10, 11, 23, 40]  is a technique to reason about input data in sequential programs. It is capable of dealing with real-world programs. Partial-Order Reductions (PORs)  [5, 43, 21, 20]  are a large family of techniques to explore a reduced number of thread interleavings without missing any relevant behavior. In this paper we propose a technique that combines symbolic execution and a Quasi-Optimal POR  [36]. In essence, our approach (1) runs the program using a symbolic executor, (2) builds a partial order representing the occurrence of POSIX threading synchronization primitives (library functions pthread_*) seen during that execution, (3) adds the partial order to an underlying tree-like, unfolding  [43, 33]  data structure, (4) computes the first events of the next partial orders to explore, and  (5)  selects a new partial order to explore and starts again.
We use cutoff events  [33]  to prune the exploration of different traces that reach the same state, thus natively dealing with non-terminating executions. We implemented our technique as an extension of KLEE. During the evaluation of this prototype we found nine bugs (that we attribute to four root causes) in the production version of memcached. All of these bugs have since been confirmed by the memcached maintainers and are fixed as of version 1. 5. 21. Our tool handles a significant portion of the POSIX threading API  [4] , including barriers, mutexes and condition variables without being significantly harder to use than common fuzz testing tools. The main challenge that our approach needs to address is that of scalability in the face of an enormous state space. We tackle this challenge by detecting whenever any two Mazurkiewicz traces reach the same program state to only further explore one of them.
Additionally, we exploit the fact that data races on non-atomic variables cause undefined behavior in C [26, § 5. 1. 2. 4  /35] , which means that any unsynchronized memory access is, strictly speaking, a bug. By adding a data race detection algorithm, we can thereby restrict thread scheduling decisions to synchronization primitives, such as operations on mutexes and condition variables, which significantly reduces the state space. This work has three core contributions, the combination of which enables the analysis of real-world multi-threaded programs (see also Sec. 6 for related work): 1. A partial-order reduction algorithm capable of handling real-world POSIX programs that use an arbitrary amount of threads, mutexes and condition variables. Our algorithm continues analysis in the face of deadlocks.
Sequential Executions Consider the program shown in Fig. 1a. Assume that all variables are initially set to zero. The statement a = in() initializes variable a non-deterministically. A run of the program is a sequence of actions, i. e. , pairs i, s where i ∈ N identifies a thread that executes a statement s. For instance, the sequence σ 1 := 1, a=in() , 1, c=3 , 2, b=c , 2, a<0 , 2, puts("n") is a run of Fig. 1a. This run represents all program paths where both statements of thread 1 run before the statements of thread 2, and where the statement a = in() initializes variable a to a negative number. In our notion of run, concurrency is represented explicitly (via thread identifiers) and data non-determinism is represented symbolically (via constraints on program variables). To keep things simple the example only has atomic integers (implicitly guarded by locks) instead of POSIX synchronization primitives.
Programs, Actions, and Runs Let P := T, L, C represent a (possibly non-terminating) multi-threaded POSIX C program, where T is the set of statements, L is the set of POSIX mutexes used in the program, and C is the set of condition variables. This is a deliberately simplified presentation of our program syntax, see App. A for full details. We represent the behavior of each statement in P by an action, i. e. , a pair i, b in A ⊆ N × B, where i ≥ 1 identifies the thread executing the statement and b is the effect of the statement. We consider the following effects: B := ({loc} × T ) ∪ ({acq, rel} × L) ∪ ({sig} × C × N) ∪ ({bro} × C × 2 N ) ∪ ({w 1 , w 2 } × C × L) Below we informally explain the intent of an effect and how actions of different effects interleave with each other. In App. B we use actions and effects to define labeled transition system semantics to P.
Implementation We implemented our approach on top of the symbolic execution engine KLEE  [10] , which was previously restricted to sequential programs. KLEE already provides a minimal POSIX support library that we extended to translate calls to pthread functions to their respective actions, enabling us to test real-world multithreaded C programs. We also extended already available functionality to make it thread-safe, e. g. , by implementing a global file system lock that ensures that concurrent reads from the same file descriptor do not result in unsafe behavior. The source code of our prototype is available at https://github. com/por-se/por-se.
External Function Calls When a program wants to call a function that is neither provided by the program itself nor by the runtime, KLEE will attempt to perform an external function call by moving the function arguments from the symbolic state to its own address space and attempting to call the function itself. While this support for uninterpreted functions is helpful for getting some results for programs which are not fully supported by KLEE's POSIX runtime, it is also inherently incomplete and not sound in the general case. Our prototype includes this option as well.
When not restricted to the program initialization, the analysis of memcached produces hundreds of thousands of events and retires hundreds of millions of instructions in less than 2 h. Our setup delivers a single symbolic packet to memcached followed by a concrete shutdown packet. As this packet can obviously only be processed once the server is ready to process input, we observe symbolic choices only after program startup is complete. (Since our prototype builds on KLEE, note that it assumes a single symbolic choice during startup, without generating an additional path. ).
However, some of the bugs found by our technique (Sec. 5) require many context switches to be reached. Bounded-model checking  [8, 41, 53, 16, 29]  for multi-threaded programs encode multiple program paths into a single logic formula, while our technique encodes a single path. Their main disadvantage is that for very large programs, even constructing the multi-path formula can be extremely challenging, often producing an upfront failure and no result. Conversely, while our approach faces path explosion, it is always able to test some program paths. Techniques like  [18, 28, 47]  operate on a data structure conceptually very similar to our unfolding. They track read/write operations to every variable, which becomes a liability on very large executions. In contrast, we only use POSIX synchronization primitives and compactly represent memory accesses to detect data races.
Conclusion Our approach combines POR and symbolic execution to analyze programs w. r. t. both input (data) and concurrency non-determinism. We model a significant portion of the pthread API, including try-lock operations and robust mutexes. We introduce two techniques to cope with state-space explosion in real-world programs. We compute cutoff events by using efficiently-computed fingerprints that uniquely identify the total state of the program. We restrict scheduling to synchronization points and report data races as errors. Our experiments found previously unknown bugs in real-world software projects (memcached, GNU sort).
4. These rules insert transitions in M P that reflect the execution of statements on individual states. As announced above, the effect of the inserted transition is in correspondence with the operation of the statement. For instance, the Loc rule inserts a transition labeled by a loc effect when it finds that a thread statement of local operation can be executed on a given LTS state. Similarly, lock, l and unlock, l operations produce transitions labeled by acq, l and rel, l effect. However, a wait, c, l action will produce two successive LTS transitions, as explained in Sec. 3. 1. The POSIX standard leaves undefined the behavior of the program under various circumstances, such as when a thread attempts to unlock a mutex not already locked by the calling thread. The rules in Fig. 4  halt the execution of the calling thread whenever undefined behavior would arise after executing an operation.
Using the standard trigonometric identity cos(a) cos(b) = 1 2 (cos(ab) + cos(a + b)), the resulting harmonics are 2) , (4. 37) so the harmonic with the lowest fraction of δλ 2). Specialising now to the case of a chain with the same resonance index k 2δλ 1,2 , (k (2) + k (1) -1)δλ 1,2 + ψ (1) 1 -ψ (2) 1 -δγ 1,2 /k (2) , (k (2) -k (1) + 1)δλ 1,2 -ψ (1) 1 + ψ (2) 1 + δγ 1,2 /k (2) , 2 (k (1) -1)δλ 1,2 + ψ (1) 1 -ψ (2) 1 -δγ 1,2 /k ( 1,2 is (k (2) -k (1) + 1)δλ 1,2 -ψ (1) 1 + ψ (2) 1 + δγ 1,2 /k ( (1) = k (2) = k, this simply gives 1 k δλ 1,2 -ψ (1) 1 + ψ (2) 1 + δγ 1,2. (4. 38) With the aid of an algebraic manipulator one can compute the full expression of {{H kepl , χ syn }, χ syn } and select the desired harmonic term (we used the software package Wolfram Mathematica), thus obtaining its coefficient (actually, one can see that this term emerges solely from the term ∝ {{1/Λ 2 2 , χ syn }, χ syn }).
We carried out the calculation with the aid of the Mathematica software in the reference case k = 3 and a 1 0. 1, which corresponds to the evolution shown in Figure  1b  (and also  Figures 2 and 3). We found that H scnd. res,kepl contains, among many others, the following terms 1. 24 × m 2 pl 2I 1 sin cos δλ 1,2 /3 + φ 1 + phase , (4. 41a) 0. 27 × m 2 pl (2I 2 ) sin cos δλ 1,2 /3 + 2φ 2 + phase , (4. 41b) 2. 39 × 10 -3 × m 2 pl 2I 1 2I 3 sin cos δλ 1,2 /3 + φ 1 + φ 3 + phase , (4. 41c) 1. 6 × m 2 pl 2I 1 2I 4 sin cos δλ 1,2 /3 + φ 1 + φ 4 + phase. (4. 41d) The nature of these harmonics is clearly general, while the numerical coefficients are specific to the reference case k = 3 and a 1 0. 1 mentioned above. We then calculated for each of the harmonics in (4. 41) their frequency δλ 1,2 /k + h• ω (m pl ) as a function of the mass.
AUTOMATIC GENERATION OF DELIVERABLES The solution for automatic generation of PSEEL's deliverables  (Coupat et al. , 2018)  dedicated to SNCF's engineers has been achieved by adapting a software package (named ODIL) to automatically generated deliverables from a graphic description which represents the PSEEL architecture. The design of such a single-line diagram (also called layout) of PSEEL is the first task of the systems engineers when handling a new a project. ODIL  (Coupat et al. , 2018)  is an automatic generation solution developed by the company Prosyst 7 and based on DSM methods (Domain Specific Modeling)  (Kelly and Tolvanen, 2008). It can be adapted to generate the required deliverables for a specific domain, in a specified format. For example, the Renault car manufacturing company has adapted ODIL to generate the required deliverables through standardization.
The templates are pieces of code specific for each PSEEL's sub-system. Step 5: Integration of the templates into the data structure of ODIL software to generate the deliverables (PSEEL and recipe book models, Uppaal models, Functional and Safety requirements, PLC programs) to be used during the second phase of verification and validation. The resulting adaptation of ODIL to PSEEL can now be used for the automatic generation of PLC programs and recipe book during an automation project (phase 1 of the new workflow in Fig. 3 ) as indicated in Figure  7. o Each electric subsystem should be connected to one or more PLC. In the case of inconsistency of input data, ODIL's interface provides information about the number and type of errors to help the engineer correct the errors. If the input data are consistent, ODIL automatically generates: 1) the target PLC programs dedicated to PSEEL's control system; and 2) the recipe books, traditionally used by engineers, for V&V of control systems in the factory.
As a result, the duration of the validation phase is reduced because any problems encountered during this phase will more likely be related to wiring errors. In this view, we have chosen to use the model checker Uppaal  (Larsen et al. , 1997). This tool offers a compact description language, a simulation module and a model-checker. The graphical representation of models and counter examples (or witnesses) returned after verification of properties facilitate the process of errors detection in PLC programs. In Uppaal, a system is represented by a collection of Timed Automata (TA). For each automaton, a given location represents a particular configuration of the model. A timed automaton can communicate with another one through binary synchronizations (or channels). To formally verify the functional and safety requirements of PLC programs, the following models are required: o The target PLC programs to be verified, translated into Uppaal language (algebraic equations).
o To avoid human errors during modeling, some of the above models are automatically generated by ODIL. For this, the data structure of ODIL has been extended to generate not only the traditional deliverables (PLC programs and recipe books, see Figure  7 ), but also the models of PSEEL electrical equipment (switch, circuit breaker…), the PLC scan cycle model and the recipe book formalized in TA (Figure  9 ). These models are then imported and grouped together in Uppaal to obtain the global model to be checked. Verification of PLC programs through model checking requires the use of a behavioral model of the PSEEL's control system that matches the program execution on the target PLC. The different models indicated above are synchronized as described in Figure  10. The initialization step is executed only during the first PLC cycle to initialize the control (SFC) programs and the PSEEL state, through a function named "initialisation()".
Automatic validation of control system (PLC programs and electric cabinets) After formal verification of PLC programs (phase 2-a), the next step (step i of phase 2-b, Figure  9 ) consists of automatic validation of PLC programs through SILS (Figure  5 ). For this, the verified (and corrected) PLC programs are transferred in SoftPLCs (communicating through shared memory protocol), connected to a Virtual Commissioning software (Figure  12 ) whose input models are automatically generated by ODIL. This Virtual Commissioning software is dedicated to validation of PSEEL's control system at SNCF. The specifications of the software have therefore been established to satisfy the requirements of SNCF engineers. The principle of automatic validation of PLC programs is based on automatic execution of test cases on the Virtual plant, controlled by softPLCs running the target PLC programs.
For this, the generated input models for Virtual Commissioning should include not only the virtual model of the target PSEEL, but also all required tests cases contained in the recipe book. These test cases are the same as those used in the formal verification phase. When the connection between softPLCs and the Virtual Commissioning software is established, the engineer can start the SILS for automatic validation of PLC programs. As in the case of formal verification with Uppaal Model Checker (phase 2-a), the validation phase stops when there exists a blocking instruction in the recipe book. Otherwise, the PLC programs are considered to be valid and ready for real commissioning. At the end of the validation phase, a report is generated with a trace of the test cases that are executed successfully the blocking test cases.
In addition to automatic execution of tests cases on virtual plant, the engineer can manually control the plant by playing specific scenarios, different from tests cases included in the recipe book. In this way, he/she can, for example, verify that the dangerous scenariospreviously identified by the model checker (during formal verification of safety requirements)cannot occur anymore further to the introduction of the safety filter. The final step of the methodology (step ii of phase 2-b, Figure  9 ) is related to the automatic validation of electric cabinets, using the same Virtual Commissioning software. Once the control program is validated, it is transferred to the PLC based control system in the factory. The PLCs involved are then connected to the Virtual Commissioning software through a physical interface that is embedded in specialized computers, called cases.
APPLICATION OF FORMAL VERIFICATION TO A TRANSFORMER GROUP This section presents an example of application of the formal verification methodology to the Transformer Group N°1, which is controlled by one PLC and presented in Figure  1. The PLC programs are designed with STRATON software (www. copalp. com) and the programming languages used  (IEC 61131-3, 2013)  are Ladder Diagram (LD) and Sequential Function Chart (SFC). The objective is to formally verify these PLC programs generated by ODIL and dedicated to control the electric subsystem. The required models are presented below. To synchronize the execution of the models and tasks, the Uppaal model presented in Figure  10  is used. This main model is represented by a timed automaton structured as a loop, which includes a clock "x" to measure the PLC scan cycle time (equal to 20 time units here).
Model of the Transformer Group In order to verify the PLC program and its integration into the plant it has to control, a model of the Transformer Group is required. This implies a thorough knowledge of the plant, particularly the behavior of each plant element and its reaction time. In a PSEEL, there exist about 20 types of devices (switches and circuits breakers), but according to their structure and behavior (inputs/outputs), these devices can be classified in 4 generic categories. To facilitate the automatic generation of PSEEL's models, the four generic devices are modeled as discrete event systems and integrated into ODIL's data structure. For a given installation, ODIL selects and generates all required models to compose the global model of the plant. The Transformer Group, as shown in Fig.
Though the transformer "Tr1" has a continuous behavior, it is modeled as a structure of Boolean variables representing internal faults, because these faults (overcurrent, short circuit, overheating. ) are the only information that the program needs. These faults are modelled as an arbitrary fault generator (figure  22 ). The above structural analysis of the Transformer Group is followed by its functional analysis to understand the behavior of the devices in order to model them in the model checker Uppaal. For example, the behavior of the switch "sect1" (device category 1) is modelled with the Uppaal timed automata presented in figure  15. The switch is initially opened, but it starts closing once it receives closing order (input "close") from its PLC program. Then, after a certain duration (TimeCL) it becomes fully closed if the order was still maintained, otherwise it returns to the initial state if the closing order was released or if opening order was activated.
Details about this model are presented in  (Niang, 2018). These control programs communicate with each other through shared variables. For formal verification, the Model-Checker Uppaal does not accept Ladder Diagram or SFC language but only textual equations or representation by automata. For programs coded into Ladder Diagram (LD), the translation into algebraic equations is trivial and consists in interpreting several simple logic functions  (Seabra et al. 2007 ). On the other hand, the SFC programs are translated into algebraic equations that are sequentially executed by computing: 1) clearing conditions of the transitions, 2) the values of the step variables, and 3) the actions  (Machado et al. ). Figure  17  presents the SFC program of the switch "sect1". The translated program, written in algebraic equations, is depicted in Figure  18.
The function of a transition, ft, is given by a conjunction of the state of the previous steps and the logical condition associated with the transition. A step is activated if the function of one of its input transitions is true. It remains active as long as the function of one of its output transitions is false. The actions associated with a step are active when the step is active. A tool has been developed for automatic translation of SFC and LD control programs into algebraic equations in Uppaal. This tool is based on the structured methodology proposed in  (Machado et al. , 2006). After the translation of the control programs, they are instantiated into the main program "computing()" which executed during any PLC cycle. The verification of functional requirements consists in verifying that the PLC program satisfies a set of test cases defined in the recipe book.
These test cases are not exhaustive enough to formally guarantee the safety of the installation. For the Transformer Group defined in Figure  1 , ten test cases are required to validate its functional requirements. Figure  19  presents the first test case, entitled "Circuit breaker's reaction after overcurrent". It consists in verifying that if an overcurrent fault appears in the Transformer Group, the circuit breaker "DJ1" remains open as long as the fault has not disappeared. To verify with Uppaal if the control program satisfies this test case, the latter should be formalized in the model checker. A test case is, somehow, similar to a SFC program, because it is mainly composed of: 1) initial condition, actions (instructions), and 2) transitions (Expected results). Thus, the formalization of a test case consists in translating it into a SFC program, and then into algebraic equations as we did for the SFC control program of the switch "sect1".