Non-Markovian Tasks (NMTs) are distinguished by their dependence on long-term memory and state-dependent dynamics, setting them apart from the traditional Markovian models typically employed in Reinforcement Learning (RL). NMTs not only suffer from reward sparseness but also rely on historical information, making their resolution considerably more challenging. In this paper, we propose a novel RL framework T4NMTD (Transition-centric framework for NMT Decomposition), designed specifically for learning NMTs which are specified by temporal logic. The core of T4NMTD is a task decomposition mechanism along with a parallel training approach for NMTs. An NMT is first decomposed as basic units based on the transitions of the automata which are derived from temporal logic formulae. The units are then modularized into sub-tasks according to their semantic similarity under logical interpretation. The training strategy of T4NMTD adopts a dual-level structure: the high-level learns to shape the boundaries and coordinate arrangement of the sub-tasks from a global perspective, while the low-level learns those sub-tasks in parallel. In addition, we invent a dynamic policy intervention scheme to mitigate the policy myopic issue during parallel training. A comprehensive evaluation is conducted on benchmark problems with respect to various metrics. The experimental results demonstrate that T4NMTD effectively addresses NMTs, achieving significant performance improvements compared with related studies.

Abstract Formal verification of Semantic Segmentation Networks is challenging due to high-dimensional output spaces and cumulative over-approximation errors in deep architectures. Existing verification methods based on specific Star-set reachability suffer from either exponential state explosion (exact splitting) or excessive conservativeness (interval-based relaxation). In this work, we present ATKVerifier , a verification framework for SSNs operating on an abstract domain named constrained-star (C-star), which captures spatial dependencies within MaxPool receptive fields through explicit predicate constraints. Our framework features: (1) an adaptive top-K lower bound mechanism that dynamically encodes K potential maximizers based on layer depth and interval overlap, balancing precision and computational cost through parameter-free adaptation; (2) an adaptive affine upper bound exploiting linear relationships between top candidates to replace conservative constant bounds; and (3) region-level completeness (RLC), a spatial robustness metric quantifying the integrity of verified contiguous object regions. Experiments on M2NIST with three SSN architectures (16 $$\sim $$ ∼ 24 layers) demonstrate 8 $$\sim $$ ∼ 25% improvement in robust Intersection-over-Union (IoU) over the ImageStar-based NNV baseline, with the improvement scaling with the network’s depth. For the 24-layer architecture, ATKVerifier achieves 59.2% RLC versus 43.8% of NNV, certifying 35.2% more complete semantic objects.

Abstract Emerson-Lei automata, which allow arbitrary Boolean combinations of $$\texttt{Fin}$$ Fin and $$\texttt{Inf}$$ Inf acceptance conditions, provide a unifying framework for $$\omega $$ ω -automata but pose significant challenges for determinization. The previous best algorithm relies on a transformation that introduces an exponential blow-up in the state space before determinization even begins. We present a new determinization algorithm that completely bypasses this bottleneck. Our key insight is that each disjunct of an Emerson-Lei condition in DNF corresponds directly to a one-Fin automaton —a restricted form of Streett automaton whose structure enables more efficient determinization via H-Safra trees. By exploiting this connection, we establish an upper bound of $$ 2^{O\!\big (3^{|\alpha |/3} \cdot (n \log n + n|\alpha | \log |\alpha |)\big )} $$ 2 O ( 3 | α | / 3 · ( n log n + n | α | log | α | ) ) where n is the number of states and $$|\alpha |$$ | α | is the acceptance condition size. This improves the exponent over the previous best bound by a factor of $$2^{2|\alpha |}/3^{|\alpha |/3}$$ 2 2 | α | / 3 | α | / 3 , an exponential improvement in the acceptance condition complexity.

Abstract In the development and verification of safety-critical aero-space software, Linear Temporal Logic (LTL) has been widely used to specify complex system properties derived from requirements. However, a significant gap remains in industrial practice: translating natural language (NL) requirements into formal LTL properties is a labor-intensive and error-prone process that requires rare expertise in both aerospace control engineering and formal methods. While recent NL-to-LTL tools ( e.g. , NL2SPEC, NL2TL, NL2LTL) are capable of automating parts of this process, they often fail on real requirement documents in industrial settings, due to complex domain terminology or implicit temporal and logical structure. To address these challenges, we present Aero Req2LTL , a framework that automates LTL property generation for aerospace requirements using large language models (LLMs), with two key industrial innovations: (i) a data dictionary that normalizes technical jargon into precise atomic propositions; and (ii) a template-based requirement language that makes temporal cues and logical relations explicit before translation. On a real aerospace dataset, Aero Req2LTL achieves 85% precision and 88% recall in LTL generation, and its outputs can be directly consumed by existing verification tools.

The technical complexity of research papers often limits their reach, necessitating more accessible formats like scientific videos to disseminate key insights through engaging narration. However, existing automated methods primarily focus on static posters or slide presentations that remain template-bound and linear. Shifting to audience-adaptive video synthesis requires addressing non-linear narrative orchestration and the joint synchronization of disparate multimodal assets. We introduce VideoAgent, a modular framework that redefines scientific video synthesis as an intent-driven planning problem. By decoupling content understanding from multimodal synthesis, VideoAgent adaptively interleaves static slides with dynamic animations to match the semantic density of the narration. We further propose SciVidEval, a benchmark evaluating multimodal quality and pedagogical utility through automated metrics and human knowledge transfer studies. Extensive experiments demonstrate that VideoAgent effectively conveys complex technical logic with high narrative fidelity and communicative impact.

Jialun Cao, Yaojie Lu, Meiziniu Li, Haoyang Ma, Haokun Li, Mengda He, Cheng Wen, Le Sun, Hongyu Zhang, Shengchao Qin, Shing-Chi Cheung, Cong Tian. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

Deep neural networks (DNNs) have become integral to numerous safety-critical applications, necessitating rigorous verification of their trustworthiness. However, the problem of verifying DNNs has high computational complexity, and existing techniques have limited efficiency, insufficient to deal with large-scale network models. To address this challenge, we propose a novel abstraction-refinement verification method that reduces network size while maintaining verification accuracy. Specifically, the method quantifies the similarity between neurons based on various factors such as their interval outputs, and then merges similar neurons to generate a smaller abstract network. In addition, a counterexample-guided refinement process is developed to mitigate the impact of potential spurious counterexamples, so that verification results from the abstract network are applicable to the original network. We have implemented this method as a tool named ARVerifier and integrated it with three state-of-the-art verification tools for evaluation on ACAS Xu and MNIST benchmarks. Experimental results demonstrate that ARVerifier significantly reduces network size and yields verification time reductions by 11.61%, 18.70%, and 12.20% compared to α,β-CROWN, Verinet, and Marabou, respectively. Moreover, ARVerifier exhibits efficiency improvements by 26.64% and 46.87% compared to existing abstraction-refinement methods NARv and CEGAR-NN, respectively.

Automated code generation has long been considered the holy grail of software engineering. The emergence of Large Language Models (LLMs) has catalyzed a revolutionary breakthrough in this area. However, existing methods that only rely on LLMs remain inadequate in the quality of generated code, offering no guarantees of satisfying practical requirements. They lack a systematic strategy for requirements development and modeling. Recently, LLM-based agents typically possess powerful abilities and play an essential role in facilitating the alignment of LLM outputs with user requirements. In this paper, we envision the first multi-agent framework for reliable code generation based on Requirements Development and Formalization, named ReDeFo. This framework incorporates three agents, highlighting their augmentation with knowledge and techniques of formal methods, into the requirements-to-code generation pipeline to strengthen quality assurance. The core of ReDeFo is the use of formal specifications to bridge the gap between potentially ambiguous natural language requirements and precise executable code. ReDeFo enables rigorous reasoning about correctness, uncovering hidden bugs, and enforcing critical properties throughout the development process.

Automating the translation of natural language (NL) software requirements into formal specifications remains a critical challenge in scaling formal verification practices to industrial settings, particularly in safety-critical domains. Existing approaches, both rule-based and learning-based, face significant limitations. While large language models (LLMs) like GPT4o demonstrate proficiency in semantic extraction, they still encounter difficulties in addressing the complexity, ambiguity, and logical depth of real-world industrial requirements. In this paper, we propose Req2LTL, a modular framework that bridges NL and Linear Temporal Logic (LTL) through a hierarchical intermediate representation called OnionL. Req2LTL leverages LLMs for semantic decomposition and combines them with deterministic rule-based synthesis to ensure both syntactic validity and semantic fidelity. Our comprehensive evaluation demonstrates that Req2LTL achieves 88.4% semantic accuracy and 100% syntactic correctness on real-world aerospace requirements, significantly outperforming existing methods.

Machine learning (ML) models are widely deployed on edge nodes, such as mobile phones and edge servers, to power a wide range of AI applications over the web. Ensuring the integrity of these edge models is paramount, as they are subject to corruption caused by software/hardware exceptions and malicious tampering, which may undermine model performance, incur economic losses, and pose health risks. Existing data integrity mechanisms designed for files stored on disks cannot properly verify the integrity of models running in GPUs or mitigate the new integrity threats against edge models. This paper proposes EdgeThemis, a novel mechanism for verifying the integrity of edge models through sentinel verification. To enable verifiability for a model M, EdgeThemis embeds a sentinel backdoor and a verification module into M. Then, a challenger can send verification requests to the edge node hosting M to verify its integrity. Next, the sentinel activates the verification module to generate a unique integrity proof tied to the identity of the edge node for verification. Finally, the challenger can verify the integrity proof to detect model corruption. Theoretical analysis proves that EdgeThemis can properly mitigate potential integrity threats against edge models. Experiments demonstrate that EdgeThemis achieves a verification accuracy of 100.00% across various models and different types of model corruption with robustness against replay attacks, theft attacks, and replacement attacks.

In an edge computing environment, data can be cached on edge servers to enable fast data services for users. These edge data are subject to corruption and must be verified to ensure their integrity. Meanwhile, they are also subject to partial content changes over time. Existing edge data integrity (EDI) schemes are designed to verify edge data as a whole. They fail to accommodate partially identical edge data and consequently suffer from low verification accuracy in many real-world applications. In the meantime, their reliability is subject to compromises caused by edge servers' Byzantine behaviors. This paper presents DynaEDI+, a novel decentralized EDI scheme capable of verifying the integrity of partially identical edge data. It introduces pairing trees, a new tree-based data digest structure, to enable subtree-based content comparison, allowing precise identification of version-matched data blocks. To reduce communication overhead, DynaEDI+ transmits only root nodes instead of entire trees for verification. It also implements a series of security mechanisms to safeguard the verification process against evasion attacks, replay attacks, and theft attacks from Byzantine edge servers. Theoretical analysis proves that DynaEDI+ can effectively defend against potential threats from Byzantine edge servers. Experimental results demonstrate that DynaEDI+ achieves high accuracy in edge environments with partially identical data and Byzantine edge servers, while reducing communication overhead by an order of magnitude compared to benchmark schemes.

Abstract Formal verification provides a rigorous and systematic approach to ensure the correctness and reliability of software systems. Yet, constructing specifications for the full proof relies on domain expertise and non-trivial manpower. In view of such needs, an automated approach for specification synthesis is desired. While existing automated approaches are limited in their versatility, i.e. , they either focus only on synthesizing loop invariants for numerical programs, or are tailored for specific types of programs or invariants. Programs involving multiple complicated data types ( e.g. , arrays, pointers) and code structures ( e.g. , nested loops, function calls) are often beyond their capabilities. To help bridge this gap, we present AutoSpec , an automated approach to synthesize specifications for automated program verification. It overcomes the shortcomings of existing work in specification versatility, synthesizing satisfiable and adequate specifications for full proof. It is driven by static analysis and program verification, and is empowered by large language models (LLMs). AutoSpec addresses the practical challenges in three ways: (1) driving AutoSpec by static analysis and program verification, LLMs serve as generators to generate candidate specifications, (2) programs are decomposed to direct the attention of LLMs, and (3) candidate specifications are validated in each round to avoid error accumulation during the interaction with LLMs. In this way, AutoSpec can incrementally and iteratively generate satisfiable and adequate specifications. The evaluation shows its effectiveness and usefulness, as it outperforms existing works by successfully verifying 79% of programs through automatic specification synthesis, a significant improvement of 1.592x. It can also be successfully applied to verify the programs in a real-world X509-parser project.

Logic rewriting is a critical and time-consuming task in logic synthesis, which determines the area and delay of the synthesized circuit. However, existing parallel solutions for this task suffer from limitations in terms of runtime or quality in large-scale complex circuits. In this paper, we propose a divide-and-conquer parallel approach namely DACPara for high-quality logic rewriting in large-scale circuits. Specifically, after nodes in AIG are divided in each level, dynamic global information is considered to divide and conquer rewriting into three stages for parallel processing. Experiments show that DACPara using 40 CPU physical cores can be 34.36x and 1.96x faster than logic rewriting in ABC and the state-of-the-art CPU parallel method on large benchmarks, respectively, with extremely comparable quality of result. Also, for large-scale complex benchmarks, compared with state-of-the-art GPU accelerated method ours can achieve 1.1% quality improvement.

Interrupt-driven programs are widely used in safety-critical fields like aerospace and embedded systems. However, the unpredictable interleaving of Interrupt Service Routines (ISRs) can lead to concurrency bugs, particularly atomicity violations when ISRs preempt atomic sequences of instructions. To address this, we propose a dynamic approach for detecting atomicity violations in interrupt-driven programs. Extensive experiments demonstrate that our method is more precise and efficient than related approaches.

Static analysis tools for capturing bugs and vulnerabilities in software programs are widely employed in practice, as they have the unique advantages of high coverage and independence from the execution environment. However, existing tools for analyzing large codebases often produce a great deal of false warnings over genuine bug reports. As a result, developers are required to manually inspect and confirm each warning, a challenging, time-consuming, and automation-essential task. This article advocates a fast, general, and easily extensible approach called Llm4sa that automatically inspects a sheer volume of static warnings by harnessing (some of) the powers of Large Language Models (LLMs). Our key insight is that LLMs have advanced program understanding capabilities, enabling them to effectively act as human experts in conducting manual inspections on bug warnings with their relevant code snippets. In this spirit, we propose a static analysis to effectively extract the relevant code snippets via program dependence traversal guided by the bug warning reports themselves. Then, by formulating customized questions that are enriched with domain knowledge and representative cases to query LLMs, Llm4sa can remove a great deal of false warnings and facilitate bug discovery significantly. Our experiments demonstrate that Llm4sa is practical in automatically inspecting thousands of static warnings from Juliet benchmark programs and 11 real-world C/C++ projects, showcasing a high precision (81.13%) and a recall rate (94.64%) for a total of 9,547 bug warnings. Our research introduces new opportunities and methodologies for using the LLMs to reduce human labor costs, improve the precision of static analyzers, and ensure software trustworthiness

The study focuses on achieving full view coverage in a camera sensor network to effectively monitor moving objects from multiple perspectives. Three key issues are addressed: camera direction selection, location selection, and moving object monitoring. There are three steps to maximize coverage of moving targets. The first step involves proposing the Maximum Group Set Coverage (MGSC) algorithm, which selects the camera sensor direction for traditional target coverage. In the second step, a composed target merged from a set of fixed directional targets represents multiple views of a moving object. Building upon the MGSC algorithm, the Maximum Group Set Coverage with Composed Targets (MGSC-CT) algorithm is presented to determine camera sensor directions that cover subsets of fixed directional targets. Additionally, a constraint on the number of cameras is imposed for camera location selection, leading to the study of the Maximum Group Set Coverage with Size Constraint (MGSC-SC) algorithm. Each of these steps formulates a problem on group set coverage and provides an algorithmic solution. Furthermore, improved versions of MGSC-CT and MGSC-SC are developed to enhance the coverage speed. Computer simulations are employed to demonstrate the significant performance of the algorithms.

Certificate parsers, which are critical components of Secure Sockets Layer or Transport Layer Security (SSL/TLS) implementations, parse incomprehensible certificates into comprehensible inputs to certificate validators and humans. Thus, certificate parsers profoundly affect decision-makings of validators and humans, which in turn affect security. To guarantee the correctness of certificate parsers, an approach for search-based differential testing of certificate parsers, namely SBDT, is put forward. SBDT begins with modeling certificate structures, mutation operations, and bounds. Based on the initial model, SBDT searches for the most promising model node and mutation operator that trigger discrepancies, and generates a certificate from the node and operator it finds. Then, SBDT feeds the certificate to certificate parsers, and searches for multiple types of discrepancies after normalizing the results output by parsers. Distinct discrepancies are employed as feedback to update and prune the model. SBDT starts the next iteration from the updated and pruned model, unless all nodes and mutation operators have been pruned due to reaching their upper bounds. Our work has the following contributions: (1) To the best of our knowledge, this is the first time that testing of certificate parsers has been clearly distinguished from testing of certificate validators, which will facilitate accurate testing of certificate parsers and validators; (2) SBDT is the first systematic and efficient approach for differential testing of certificate parsers by searching, updating, and pruning models; and (3) We have implemented an open-source prototype tool of SBDT, and experimental results show that SBDT is effective and efficient in finding new bugs and enhancements of certificate parsers.

Adversarial training (AT) is one of the most effective ways for deep neural network models to resist adversarial examples. However, there is still a significant gap between robust training accuracy and testing accuracy. Although recent studies have shown that data augmentation can effectively reduce this gap, most methods heavily rely on generating large amounts of training data without considering which features are beneficial for model robustness, making them inefficient. To address the above issue, we propose a two-stage AT algorithm for image data that adopts different data augmentation strategies during the training process to improve model robustness. In the first stage, we focus on the convergence of the algorithm, which uses structure and texture information to guide AT. In the second stage, we introduce a strategy that randomly fuses the data features to generate diverse adversarial examples for AT. We compare our proposed algorithm with five state-of-the-art algorithms on three models, and the experimental results achieve the best robust accuracy under all evaluation metrics on the CIFAR10 dataset, demonstrating the superiority of our method.

Interrupt-driven programs have been widely used in safety-critical areas such as aerospace and embedded systems. However, uncertain interleaving execution of interrupt service routines (ISRs) usually causes concurrency bugs. Specifically, when one or more ISRs attempt to preempt a sequence of instructions which are expected to be atomic, a kind of concurrency bugs namely atomicity violation may occur, and it is challenging to find this kind of bugs precisely and efficiently. In this paper, we propose a static approach for detecting atomicity violations in interrupt-driven programs. First, the program model is constructed with interruption points being selected to determine the possibly influenced ISRs. After that, reachability computation is conducted to build up a whole abstract reachability tree, and a delayed ISR-triggering strategy is employed to reduce the state space. Meanwhile, unserializable interleaving patterns are recognized to achieve the goal of atomicity violation detection. The approach has been implemented as a configurable tool namely CPA4AV. Extensive experiments show that CPA4AV is much more precise than the relative tools available with little extra time overhead. In addition, more complex situations can be dealt with CPA4AV.

Abstract is a tool for verifying reachability properties of concurrent C programs. It moderates the trace-space explosion problem, aggravated by thread alternation, through utilizing the PC-DPOR and C-Intp techniques. The PC-DPOR technique constructs a constrained dependency graph to refine dependencies between transitions. With this basis, the inherent imprecision of the dependence over-approximation can be overcome. Thereby, many redundant equivalent traces are prevented from being explored. On the other hand, the C-Intp technique performs conditional interpolation to confine the reachable regions of states, so that infeasible conditional branches which occur more frequently in concurrent verification tasks could be pruned automatically. We have implemented the above techniques on top of the open-source program analysis framework .

Smart contract, a special software code running on and resided in the blockchain, enlarges the general application of blockchain and exchanges assets without dependence of external parties. With blockchain’s characteristic of immutability, they cannot be modified once deployed. Thus, the contract and the records are persisted on the blockchain forever, including failed transactions that are caused by runtime errors and result in the waste of computation, storage, and fees. In this paper, we refer to smart contracts which will cause runtime errors as crash-inducing smart contracts. However, automatic identification of crash-inducing smart contracts is limited investigated in the literature. The existing approaches to identify crash-inducing smart contracts are either limited in finding vulnerability (e.g., pattern-based static analysis) or very expensive (e.g., program analysis), which is insufficient for Ethereum.To reduce runtime errors on Ethereum, we propose an efficient, generalizable, and machine learning-based crash-inducing smart contract detector, CRASHSCDET, to automatically identify crash-inducing smart contracts. To investigate the effectiveness of CRASHSCDET, we firstly propose 34 static source code metrics from four dimensions (i.e., complexity metrics, count metrics, object-oriented metrics, and Solidity-specific metrics) to characterize smart contracts. Then, we collect a large-scale dataset of verified smart contracts (i.e., 54,739) and label these smart contracts based on their execution traces on Etherscan. We make a comprehensive comparison with three state-of-the-art approaches and the results show that CRASHSCDET can achieve good performance (i.e., 0.937 of F1-measure and 0.980 of AUC on average) and statistically significantly improve the baselines by 0.5%-60.4% in terms of F1-measure and by 41.2%-44.3% in terms of AUC, which indicates the effectiveness of static source code metrics in identifying crash-inducing smart contracts. We further investigate the importance of different types of metrics and find that metrics in different dimensions have varying abilities to depict the characteristic of smart contracts. Especially, metrics belonging to the "Count" dimension are the most discriminative ones but combining all metrics can achieve better prediction performance.

As a lightweight method, runtime verification aims to check whether one program execution satisfies a desired property. For online runtime verification, the approach efficiency and property expressiveness are two key points restricting its wide application. In this paper, we propose a distributed network-based parallel runtime verification approach to verifying full regular temporal properties for a suitable subset of C (named by Xd-C) programs in an online manner. With this approach, an Xd-C program is translated into an equivalent Modeling, Simulation and Verification Language (MSVL) program, and a desired property is specified as a Propositional Projection Temporal Logic (PPTL) formula; during the program execution, segments of the generated state sequence are verified in parallel by distributed multi-core machines. Experimental results show that, our approach has a speedup of 2.5X-5.0X over the state-of-art runtime verification approaches and supports full regular temporal properties, meaning that our approach can not only take full advantage of computing and storage resources in a distributed network, but also support more expressive properties.

Thread alternation aggravates the difficulty of concurrent program verification since the number of traces to be explored grows rapidly as the scale of a concurrent program increases. Partial-Order Reduction (POR) techniques alleviate the trace-space explosion problem by partitioning the traces into different equivalent classes. However, due to the coarse dependency approximation of transitions, there are still a large number of redundant traces explored throughout the verification. In this paper, a symbolic approach, namely Prioritized Constraint-Aided Dynamic Partial-Order Reduction (PC-DPOR), is proposed to reduce the redundant traces. Specifically, a constrained dependency graph is presented to refine dependencies between transitions, and the exploration of isolated transitions in the graph is prioritized to reduce redundant equivalent traces. Further, we utilize the generated constraints to dynamically detect whether the enabled transitions at the given reachable states are dependent, and thereby to overcome the inherent imprecision of the traditional dependence over-approximation. We have implemented the proposed approach as an extension of CPAchecker by utilizing BDDs as the representation of state sets. Experimental results show that our approach can effectively reduce the time and memory consumption for verifying concurrent programs. In particular, the number of explored states is reduced to 8.62% on average.

The software defect prediction method based on requirement specification is proposed to address the defect prediction needs in the requirements phase when the organization adopts the W-model of software development. The theoretical synthesis presents that the function point and the number of defects should be positively correlated. The theory’s correctness is verified by analyzing the correlation between function point and defect distribution of eight software applications. Then, the mathematical equations for software configuration testing defects are derived, and the specific meaning of the equation is explained. Finally, the shortcomings of this study and the subsequent research directions are pointed out.

Big data techniques are widely used in various fields. To deal with large data sets efficiently, a new programming framework MapReduce has emerged. Thus, new verification challenges arise to improve the reliability of big data processing. In this article, MapReduce processes are implemented by modeling simulation and verification language programs. Then, several data properties such as data soundness, nonconflict, nonduplication, cooperation, and completeness are taken into account. Moreover, these properties are specified by propositional projection temporal logic formulas. To verify these properties, a runtime verification approach at code level based on unified model checking is employed. In addition, two case studies are conducted to demonstrate our approach: sparse matrix multiplication and tracking down suspected patients of an infectious disease.

There is a wide agreement that model checking and automated planning (planning for short) are closely related fields. Planning is the task of finding a sequence of appropriate moves that achieves a goal. Model checking aims to prove or disprove a system model that satisfies a given property which is often specified by temporal logics. In this paper we investigate the application of advanced planning techniques to model checking. To this end, a system model is expressed by means of a planning model, and temporal logic property can be treated as a special form of planning goal, i.e., Temporally Extended Goal (TEG). Therefore, the model checking task can be reduced into a planning scheme what we call planning with TEG. In order to utilize the state-of-the-art planners, we further propose two novel compilation methods to translate a planning with TEG problem into a classical planning problem and a non-deterministic planning one respectively. The obtained valid plans in planning just correspond to the counterexamples in model checking. We provide detailed evaluations of our approach on a series of benchmarks. The experimental results are encouraging, showing that existing planners can provide significant improvements in the quality of the counterexamples compared with the model checkers.

Due to the state-space explosion problem, efficient verification of real-world programs in large scale is still a big challenge. Particularly, thread alternation makes the verification of concurrent programs much more difficult since it aggravates this problem. In this paper, an application of Craig interpolation, namely conditional interpolation, is proposed to work together with CEGAR-based approach to reduce the state-space of concurrent tasks. Specifically, conditional interpolation is formalized to confine the reachable region of states so that infeasible conditional branches could be pruned. Furthermore, the generated conditional interpolants are utilized to shorten the interpolation paths, which makes the time consumed for verification significantly reduced. We have implemented the proposed approach on top of an open-source software model checker. Empirical results show that the conditional interpolation is effective in improving the verification efficiency of concurrent tasks.

The global trends in urbanization have caused many problems, among which Urban Traffic Control (UTC) becomes a priority issue for most big cities in many countries. As traffic demand changes rapidly, appropriate control policies are required to be generated in real time in order to, e.g., minimize congestion to reduce average travel time and air pollution. A practical way to meet the challenge is to build an intelligent control mechanism of road traffic. In this context, automated planning, a powerful and effective technique, can be exploited as an aid to dynamically produce plans to alleviate the problems of UTC. In this paper, we present an approach based on automated planning, in particular temporal planning scheme that aims for producing predictable management strategies of UTC. Meanwhile, a logic style control knowledge is employed to provide useful guidance for the search process in planning. We show the preliminary evaluations on simulation benchmarks closely related to UTC. Experimental results show the feasibility and effectiveness of our approach, compared with the state-of-the-art planners that participate in recent International Planning Competitions.

In this article, we present an approach based on counterexample-guided abstraction refinement to verifying full regular temporal properties of C programs by means of combining both static analysis and dynamic verification. To this end, a desired property is specified by a propositional projection temporal logic formula$p$, and the labeled normal form graph (LNFG) of$\lnot p$is automatically produced. Furthermore, the control flow automaton of the C program is constructed, and an enriched abstract reachability tree is generated under the guidance of the LNFG. Throughout the construction of the eART, whenever a candidate counterexample$cp$is found, a verification input w.r.t$cp$is generated by the SMT solver Z3. Subsequently, the C program is converted into a modeling, simulation, and verification language (MSVL) program$m$, and$\lnot p$is also transformed to an MSVL program$m^{\prime }$. As a result,$m\; \text{and} \;m^{\prime }$is executed to check whether the counterexample is spurious. The$cp$is returned if it is a real counterexample; otherwise, the eART is refined. This process is repeated until no counterexample is found, namely the property is valid, or the counterexample is a real one The proposed approach enables us to not only verify full regular properties of C programs, but also produce precise results, neither false negatives nor false positives. The approach has been implemented in a tool named SDMC. Experiments show that SDMC outperforms the relevant tools available.

In Android 6.0 and above, the install-time permission model is replaced with the runtime permission model (RPM), where permission requesting is performed at runtime, rather than at install time, to protect users' privacy. The RPM brings certain benefits to security, but still has drawbacks that are exploitable by malware. The permission could be attained under a reasonable context and then be freely used under another context for executing malicious behavior without notifying users. In addition, the RPM may cause bugs when developers forget to add permission checking before using it. Motivated by this, we propose RTPDroid, an approach to detect implicitly malicious behaviors and bugs brought by the RPM. To do so, implicitly malicious behaviors and bugs are defined formally. Then, notions of user-aware contexts as well as user-aware call graphs are defined and utilized for the detection. Experiments on 221 real-world apps reveal 131 bugs and 174 implicitly malicious behaviors under the RPM.

Optimal determinization construction of Streett automata is an important research problem because it is indispensable in numerous applications such as decision problems for tree temporal logics, logic games and system synthesis. This paper presents a transformation from nondeterministic Streett automata (NSA) with n states and k Streett pairs to equivalent deterministic Rabin transition automata (DRTA) with n5n(n!)n states, O(nn2) Rabin pairs for k = ω(n) and n5nknk states, O(knk) Rabin pairs for k = O(n). This improves the state of the art Streett determinization construction with n5n(n!)n+1 states, O(n2) Rabin pairs and n5nknkn! states, O(nk) Rabin pairs, respectively. Moreover, deterministic parity transition automata (DPTA) are obtained with 3(n(n + 1) -- 1)!(n!)n+1 states, 2n(n +1) priorities for k = ω(n) and 3(n(k +1) -- 1)!n!knk states, 2n(k + 1) priorities for k = O(n), which improves the best construction with nn(k + 1)n(k+1)(n(k + 1) -- 1)! states, 2n(k + 1) priorities. Further, we prove a lower bound state complexity for determinization construction from N-SA to deterministic Rabin (transition) automata i.e. n5n(n!)n for k = ω(n) and n5nknk for k = O(n), which matches the state complexity of the proposed determinization construction. Besides, we put forward a lower bound state complexity for determinization construction from NSA to deterministic parity (transition) automata i.e. 2ω(n2 log n) for k = ω(n) and 2ω(nk log nk) for k = O(n), which is the same as the state complexity of the proposed determinization construction in the exponent.

In Android 6.0 and above, Install-time Permission Model is replaced with Runtime Permission Model (RPM) where permission requesting is performed at runtime, rather than at install-time, to protect users' privacy. RPM brings certain benefits to security, but still has drawbacks that are exploitable by malware. The permission could be attained under a reasonable context and then be freely used under another context for executing malicious behavior without notifying users. In addition, RPM may cause bugs when developers forget to add permission checking before using the permission. Motivated by these problems, we propose RTPDroid, an approach to the detection of implicitly malicious behaviors and bugs brought by RPM. In this approach, these implicitly malicious behaviors and bugs are defined formally. Then, notions of user-aware contexts as well as user-aware call graphs are utilized for the detection. Experiments on 221 real-world apps reveal 131 bugs and 174 implicitly malicious behaviors under RPM.

In this paper, we propose a shared-memory parallel field-programmable gate array (FPGA) router called ParRA. Basically, ParRA is composed of hybrid partitioning and parallel routing. During the hybrid partitioning, first an FPGA is split into multiple subregions and nets are geographically partitioned into local subsets. As the intersubregion nets usually overlap each other, these nets cannot be routed in parallel. Second, the intersubregion nets are further partitioned into conflict-free subsets. Since each conflict-free subset consists of intersubregion nets do not overlap each other, the nets in the same conflict-free subset can be routed in parallel. In this way, we significantly increase the number of nets that have potential to be routed in parallel. During the parallel routing process, two novel parallel routing strategies are applied to route the nets in conflict-free and local subsets, respectively. With conflict-free subsets, sinks in the same conflict-free subset are routed in parallel while conflict-free subsets are routed one by one. On the contrast, local subsets are routed in parallel while the nets in the same local subset are routed sequentially. With the two different parallel routing strategies, we reduce the interference between threads and balance the workload of threads, which contributes to gain more parallelism. The proposed parallel router provides deterministic routing results. The experimental results show that ParRA achieves an average speedup of $24.3 {\times }$ with 16 threads compared to VPR 7.0, has no negative impact on the quality of results.

Certificate validation in Secure Sockets Layer or Transport Layer Security protocol (SSL/TLS) is critical to Internet security. Thus, it is significant to check whether certificate validation in SSL/TLS implementations is correctly implemented. With this motivation, we propose a novel differential testing approach that is based on the standard Request for Comments (RFC). First, rules of certificates are extracted automatically from RFCs. Second, low-level test cases are generated through dynamic symbolic execution. Third, high-level test cases, i.e., certificates, are assembled automatically. Finally, with the assembled certificates being test cases, certificate validations in SSL/TLS implementations are tested to reveal latent vulnerabilities or bugs. Our approach named RFCcert has the following advantages: (1) certificates of RFCcert are discrepancy-targeted, since they are assembled according to standards instead of genetics; (2) with the obtained certificates, RFCcert not only reveals the invalidity of traditional differential testing but also is able to conduct testing that traditional differential testing cannot do; and (3) the supporting tool of RFCcert has been implemented and extensive experiments show that the approach is effective in finding bugs of SSL/TLS implementations. In addition, by providing seed certificates for mutation approaches with RFCcert, the ability of mutation approaches in finding distinct discrepancies is significantly enhanced.

Verification of programs at code level has attracted more and more attentions since the cost is high to extract models from source code. Most of approaches available for code level verification are carried out by inserting assertions into programs and then checking whether the assertions are violated. In this way, only safety properties can be verified, however, other temporal properties of programs such as liveness are hard to be verified. To tackle this problem, a novel runtime verification approach, which can verify full regular temporal properties of a program, is proposed in this paper. With this approach, a program to be verified is written in a modeling, simulation and verification language (MSVL) as a program M and a desired property is specified by a propositional projection temporal logic formula P . The negation of the desired property is then translated to an MSVL program M'. Thus, whether M violates P can be checked by evaluating whether there exists an acceptable execution of the new MSVL program “M and M'.” This problem can efficiently be solved with the MSVL compiler where verification cases are generated via dynamic symbolic execution. Further, we adopt parallel mechanism to handle various execution paths of a program for improving the efficiency. The proposed approach has been implemented in a tool called MSV. Experiments show that the performance of MSV outperforms existing tools such as T2, RiTHM, and LTLAutomizer in verifying temporal properties of real-world programs.

Certificate validation in Secure Socket Layer or Transport Layer Security protocol (SSL/TLS) is critical to Internet security. Thus, it is significant to check whether certificate validation in SSL/TLS is correctly implemented. With this motivation, we propose a novel differential testing approach which is directed by the standard Request For Comments (RFC). First, rules of certificates are extracted automatically from RFCs. Second, low-level test cases are generated through dynamic symbolic execution. Third, high-level test cases, i.e. certificates, are assembled automatically. Finally, with the assembled certificates being test cases, certificate validations in SSL/TLS implementations are tested to reveal latent vulnerabilities or bugs. Our approach named RFCcert has the following advantages: (1) certificates of RFCcert are discrepancy-targeted since they are assembled according to standards instead of genetics; (2) with the obtained certificates, RFCcert not only reveals the invalidity of traditional differential testing but also is able to conduct testing that traditional differential testing cannot do; and (3) the supporting tool of RFCcert has been implemented and extensive experiments show that the approach is effective in finding bugs of SSL/TLS implementations.

In this paper, we present a new field-programmable gate array (FPGA) routing approach on the basis of the PathFinder routing algorithm. During each routing iteration, our approach applies a novel timing-based rerouting strategy to only reroute the illegal paths. At a lower level, each maze expansion is started from the relatively close part of current routing tree to search for the target sink on the routing resource graph. Experimental results demonstrate that on average the proposed approach reduces the routing runtime by 68.5% compared with the timing-driven router in versatile place and route FPGA placement and routing framework, with reduction of 2.5% and 1.4% in critical path delay and wirelength, respectively.

Knowledge based approaches developed for AI planning can convert an intractable planning problem to a tractable one. Current techniques often use temporal logics to express Search Control Knowledge (SCK) in logic based planning. However, traditional temporal logics are limited in expressiveness since they are unable to express spatial constraints which are as important as temporal ones in many planning domains. To this end, we propose a two-dimensional (spatial and temporal) logic namely PPTLSL by temporalizing separation logic with PPTL (Propositional Projection Temporal Logic) which is well-suited to specify SCK involving both spatial and temporal constraints in planning. We prove that PPTLSL is decidable essentially via an equisatisfiable translation from PPTLSL to its restricted form. Moreover, we implement a tool, S-TSolver, which effectively computes plans under the guidance of the spatio-temporal SCK expressed by PPTLSL formulas. The effectiveness of the tool is evaluated on selected benchmark domains from the International Planning Competition.

This paper proposes a novel approach to modeling and verifying real-time systems for high reliability. To do so, we first extend projection temporal logic to timed projection temporal logic. Further, we define a timed modeling, simulation, and verification language (TMSVL) for real-time systems. As a result, both systems and desired properties can be expressed in TMSVL. In particular, real-time behaviors such as delay, timeout, and interrupt can be formalized. Compared with commonly used property specification language, TMSVL is capable of specifying more sophisticated properties such as quantitative timing properties, interval-related properties, and periodically repeated properties. Moreover, the unified model checking approach to verifying real-time systems via dynamical program execution is implemented. In addition, a case study for modeling and verifying a μC/OS-III multitask system with interrupt is conducted to demonstrate how the proposed approach works.

Temporal logics are widely adopted in Artificial Intelligence (AI) planning for specifying Search Control Knowledge (SCK). However, traditional temporal logics are limited in expressive power since they are unable to express spatial constraints which are as important as temporal ones in many planning domains. To this end, we propose a two-dimensional (spatial and temporal) logic namely PPTL^SL by temporalising separation logic with Propositional Projection Temporal Logic (PPTL). The new logic is well-suited for specifying SCK containing both spatial and temporal constraints which are useful in AI planning. We show that PPTL^SL is decidable and present a decision procedure. With this basis, a planner namely S-TSolver for computing plans based on the spatio-temporal SCK expressed in PPTL^SL formulas is developed. Evaluation on some selected benchmark domains shows the effectiveness of S-TSolver.

An approach to CEGAR-based model checking which has proved to be successful on large models employs Craig interpolation to efficiently construct parsimonious abstractions. Following this design, we introduce new applications, universal safety interpolant and existential error interpolant, of Craig interpolation that can systematically reduce the program state space to be explored for safety verification. Whenever the universal safety interpolant is implied by the current path, all paths emanating from that location are guaranteed to be safe. Dually whenever the existential error interpolant is implied by the current path, there is guaranteed to be an unsafe path from the location. We show how these interpolants are computed and applied in safety verification. We have implemented our approach in a tool named InterpChecker by building on an open source software model checker. Experiments on a large number of benchmark programs show that both the interpolations and the auxiliary optimization strategies are effective in improving scalability of software model checking.

OSEK/VDX, a standard of automobile OS, has been widely adopted by many manufacturers to design and implement a vehicle-mounted OS. Currently, with increasing functionalities in vehicles, more and more complex applications are developed based on the OSEK/VDX OS. However, how to ensure the reliability of developed applications is becoming a challenge for developers. Based on our previous work, in this paper we present an efficient approach to verify the developed OSEK/VDX applications. In the presented approach, SMT-based bounded model checking technique is used to carry out verification in order to handle complex applications. Moreover, a series of optimization strategies are proposed and employed to improve the checking capability of our approach. We have implemented a tool according to the proposed approach and conducted many experiments. The experiment results show that our approach is capable of checking the safety property of large-scale OSEK/VDX applications. We also compared our approach with existing checking method, the comparison results indicate that our approach is an efficient and powerful technique in verifying OSEK/VDX applications.

As Android platform becomes more and more popular, a large amount of Android applications have been developed. When developers design and implement Android applications, power consumption management is an important factor to consider since it affects the usability of the applications. Thus, it is important to help developers adopt proper strategies to manage power consumption. Interestingly, today, there is a large number of Android application repositories made publicly available in sites such as GitHub. These repositories can be mined to help crystalize common power management activities that developers do. These in turn can be used to help other developers to perform similar tasks to improve their own Android applications.

It is of great importance to ensure the correctness and reliability of the scheduling protocol of safety-critical systems since the failure will cause serious damage. This paper analyzes a real time scheduling protocol of the safety-critical system and models it using a Modeling, Simulation and Verification Language program. Then the sufficient and necessary conditions for the schedulability are given. Further, the schedulability and other properties are verified using the MSV toolkit.

Peer-to-Peer(P2P) reputation systems are essential to evaluate the trustworthiness of the nodes in a P2P system. This paper presents a distributed algorithm HP2PSORT based on SORT that enables a node to estimate the trustworthiness of other nodes based on the past interactions and recommendations. In an HP2P network, by using the filtering mechanism, the calculation method of the service trust and the dynamic calculation of the threshold value, we show that HP2PSORT outperforms SORT.

The paging mechanism is widely used in most modern systems to handle the virtual memory. Many page replacement algorithms have been proposed. Therefore, the cor-rectness and reliability of virtual memory management systems become very important. It is essential to formalize and verify the system in a formal way. In this paper, we model the virtual memory management system with MSVL, which is a parallel programming language used for the modeling, simulation and verification of software and hardware systems. Then we employ the model checking approach based on MSVL to verify the interval related properties and periodic repeated properties of the system.

This paper presents a model checking-based schedulability checking approach for Rate-Monotonic Scheduling (RMS) algorithm. To do so, RMS algorithm is modelled with TMSVL, and the desired property, i.e. Schedulability, is specified with the property specification language in TMSVL. Next, whether RMS algorithm is schedulable on a set of tasks is verified by checking whether the desired property is valid on the TMSVL model. A significant advantage of TMSVL is the mechanism of adjustable time intervals which makes an effective reduction on the state space.

Nowadays, software developers often discuss the usage of various APIs in online forums. Automatically assigning pre-defined semantic categorizes to API discussions in these forums could help manage the data in online forums, and assist developers to search for useful information. We refer to this process as content categorization of API discussions. To solve this problem, Hou and Mo proposed the usage of naive Bayes multinomial, which is an effective classification algorithm.

A clustering and partition based Boolean satisfiability solving method is proposed. By partitioning a CNF formula into several clause groups, satisfiability solving problem can be divided into small ones, so the complexity of the problem can be reduced. On the other hand, the satisfiability of different clause groups can be solved in parallel, the decision procedure can be speeded up further. For the formula that cannot generate clause group partition directly, a clustering algorithm is given to clustering clauses into clusters. Then clause group partition can be generated by eliminating common variables among clusters. Further, a method based on minimum cut of undirected graph is given to make partition practical. Preliminary experiments shows that the common variables set among clusters is small for many SAT problems, and our approach can significantly increase the performance of SAT solving.

An improved recursive algorithm is presented in this paper for reducing the number of recursive calls in parity games. The improvement is two-fold: (1) A pre-processing algorithm is presented first to seek out and remove atomic winning regions which probably result in exponentially many recursive calls from a game graph, (2) a conditional statement is inserted before the second recursive call of the existing algorithm where in case the condition is satisfied, the result can be obtained directly without executing the second recursive call.

Counter-example guided abstraction refinement (CEGAR) is widely used in software model checking. With an abstract model, the state space is largely reduced, however, a counterexample found in such a model that does not satisfy the desired property may not exist in the concrete model. Therefore, how to check whether a reported counterexample is spurious is a key problem in the abstraction-refinement loop. Next, in the case that a spurious counterexample is found, the abstract model needs to be further refined where an NP-hard state separation problem is often involved. Thus, how to refine the abstract model efficiently has attracted a great attention in the past years. In this paper, by re-analyzing spurious counterexamples, a new formal definition of spurious paths is given. Based on it, efficient algorithms for detecting spurious counterexamples are presented. By the new algorithms, when dealing with infinite counterexamples, the finite prefix to be analyzed will be polynomially shorter than the one dealt with by the existing algorithms. Moreover, in practical terms, the new algorithms can naturally be parallelized that enables multi-core processors contributes more in spurious counterexample checking. In addition, a novel refining approach by adding extra Boolean variables to the abstract model is presented. With this approach, not only the NP-hard state separation problem can be avoided, but also a smaller refined abstract model can be obtained. Experimental results show that the new algorithms perform well in practice.

This paper presents an approach to simulate and verify the CTCS-3 (Chinese Train Control System 3) protocol with a Modeling, Simulation and Verification Language (MSVL) which is an executable subset of Projection Temporal Logic (PTL). First, the syntax and semantics of PTL and MSVL are briefly introduced. Then, CTCS-3 protocol is briefly presented and a simplified CTCS-3 protocol described by an MSVL program is given, and the property to be verified is specified by a Propositional Projection Temporal Logic (PPTL) formula. Finally, the simulation is conducted by means of the interpreter of MSVL. A dynamic graph showing behavior of train is depicted. Based on the graph, we can verify whether or not the protocol satisfies the property.

Abstraction is one of the most important strategies for dealing with the state space explosion problem in model checking. With an abstract model, the state space is largely reduced, however, a counterexample found in such a model that does not satisfy the desired property may not exist in the concrete model. Therefore, how to check whether a reported counterexample is spurious is a key problem in the abstraction-refinement loop. Particularly, there are often thousands of millions of states in systems of industrial scale, how to check spurious counterexamples in these systems practically is a significant problem. In this paper, by re-analyzing spurious counterexamples, a new formal definition of spurious path is given. Based on it, efficient algorithms for detecting spurious counterexamples are presented. By the new algorithms, when dealing with infinite counterexamples, the finite prefix to be analyzed will be polynomially shorter than the one dealt by the existing algorithm. Moreover, in practical terms, the new algorithms can naturally be parallelized that makes multi-core processors contributes more in spurious counterexample checking. In addition, by the new algorithms, the state resulting in a spurious path (false state) that is hidden shallower will be reported earlier. Hence, as long as a false state is detected, lots of iterations for detecting all the false states will be avoided. Experimental results show that the new algorithms perform well along with the growth of system scale.

This paper presents a symbolic model checking algorithm for Propositional Projection Temporal Logic (PPTL). Within this method, the model of a system is specified by aKripke structure M, and the desired property is specified in aPPTL formula P. First, Mis symbolically represented with Boolean functions while !P is transformed into its normal form. Then the set of states in Mthat satisfies !P, namely Sat(!P), is computed recursively with respect to the transition relations. Thus, whether the system satisfies the property can be equivalently checked by determining the emptiness of Sat(!P). All the operations above can be implemented by a graph algorithm operated on ROBDDs.

Focus game is applied to Prepositional Projection Temporal Logic with infinite models (PPTL) for the satisfiability and model checking of PPTL formulas. To this end, normal form and complete normal form are introduced, and through which sub-formulas are defined for PPTL formulas. Accordingly, focus game G(R) is constructed for checking the satisfiability of PPTL formula R; and G(s,R) is built for checking whether a system with s being the initial state satisfies formula R. Finally, complexity of the decision procedure and the model checking algorithm is analyzed.

This paper investigates the complexity of Propositional Projection Temporal Logic with Star (PPTL*). To this end, Propositional Projection Temporal Logic (PPTL) is first extended to include projection star. Then, by reducing the emptiness problem of star-free expressions to the problem of the satisfiability of PPTL* formulas, the lower bound of the complexity for the satisfiability of PPTL* formulas is proved to be non-elementary. Then, to prove the decidability of PPTL*, the normal form, normal form graph (NFG) and labelled normal form graph (LNFG) for PPTL* are defined. Also, algorithms for transforming a formula to its normal form and LNFG are presented. Finally, a decision algorithm for checking the satisfiability of PPTL* formulas is formalised using LNFGs.