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.

As WebAssembly (Wasm) smart contracts are widely deployed in blockchain platforms such as EOSIO, the threat of vulnerability attacks has become increasingly significant. Protecting the legitimate interests of blockchain users necessitates robust vulnerability detection approaches. Despite the advancements in existing approaches, several challenges remain, including state dependency, cross-function state transfer, and path selection. To tackle these issues, we introduce a novel concolic fuzzing approach called WASDAM, which integrates data access modeling, dynamic sensitive code tracing, and shortest path optimization to enhance the effectiveness of vulnerability detection. We have developed an open-source prototype of WASDAM and performed comprehensive experimental evaluations. The evaluation results demonstrate that WASDAM detects vulnerabilities in Wasm smart contracts more effectively than the state-of-the-art concolic fuzzer WASAI in terms of various performance metrics.

Automated verification of interrupt-driven programs presents significant challenges, as interrupt signals can arrive at arbitrary times and preempt the execution of the current task. This requires considering a vast number of possible execution paths during verification. Furthermore, multiple interrupts may be pending simultaneously, with their service order determined by interrupt priorities. This can lead to nested preemption, further increasing the complexity of the program state space and the difficulty of verification. We propose a formal method based on partial order modeling to verify interrupt-driven programs. Our approach models the interactions among multiple tasks in interrupt-driven programs through partial orders, encoding program execution paths as logical formulas composed of partial order constraints. These formulas are then solved by an SMT solver capable of handling partial order constraints, enabling assertion checking within interrupt-driven programs. We have implemented the proposed method in a prototype tool called DIDP and conducted experiments using a benchmark dataset consisting of real-world embedded system code and device drivers to evaluate its performance. Experimental results demonstrate that, compared to state-of-theart verification tools, DIDP significantly improves verification efficiency while maintaining accuracy.

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.

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.

Attacks exploiting vulnerabilities in EOSIO smart contracts have caused serious economic losses. To detect these vulnerabilities, some approaches have been proposed, and concolic fuzzing is one of the most popular techniques among them. However, the existing concolic fuzzers have problems such as path explosion and adopting redundant constraint solving strategies, which reduce the detection efficiency. In order to alleviate these problems, we propose a demand-driven concolic fuzzing approach to discovering vulnerabilities in EOSIO smart contracts. In the approach, execution information is first collected to guide the execution of the system in a demand-driven manner. To improve the efficiency of vulnerability detection, we design a pruning strategy to eliminate the paths that are not relevant to the discovery of vulnerabilities and redundant paths to be explored. Meanwhile, an incremental constraint solving method is used to process only paths that can explore new branches. In addition, we also design a path prioritization method to preferentially explore paths which are more conducive to discovering vulnerabilities, so as to find vulnerabilities in smart contracts as early as possible. We have implemented our approach in a tool called WASAIUP and evaluated it on 3441 smart contracts. The experimental results show that WASAIUP improves the performance by 25.1% to 149.8% compared with the state-of-the-art tool WASAI in terms of efficiency, while maintaining high detection accuracy.

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.

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.

As one of the representative Delegated Proof-of-Stake (DPoS) blockchain platforms, EOSIO blockchain platform is developing rapidly in recent years due to its excellent features, such as the scalability of transaction speed and support for smart contracts and decentralized applications. However, vulnerabilities in EOSIO smart contracts have caused serious economic losses and moreover vulnerability detection tools for EOSIO contracts are limited. To overcome the above shortcomings, we implement a grey-box fuzzer called GFuzzer based on WebAssembly for smart contracts on the EOSIO platform considering that EOSIO contracts are not open-sourced. In order to generate more test cases for branches that are difficult to cover, GFuzzer selects test cases with the minimum distance to explore uncovered branches for mutation. We evaluate GFuzzer on 3963 real-world smart contracts and the experimental results show that GFuzzer can detect more vulnerabilities in EOSIO contracts than the existing tools EOSFuzzer and EVulHunter, and is efficient in achieving high branch coverage during vulnerability detection.

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.

Smart contracts are commonly used to build finance-related decentralized applications. If a smart contract vulnerability is exploited by an attacker, the contract owner may suffer financial losses. We focus on a particular class of smart contract vulnerabilities that require a specific sequence of multiple transactions to trigger, which we call multi-transaction sequence vulnerabilities. Due to the combinatorial explosion problem caused by the huge number of possible transaction sequences, the efficiency and scalability for existing security analyzers to detect multi-transaction sequence vulnerabilities are limited. To alleviate the problem, we propose a vulnerability detection approach based on symbolic execution and inter-path data dependency. In the approach, we first traverse paths in a contract, and record read and write operations of each path. Then, we selectively execute paths which are conducive to discovering vulnerabilities during the subsequent detection process according to inter-path data dependencies. By pruning out most paths that are not relevant to vulnerabilities, we improve the efficiency and scalability of detecting multi-transaction sequence vulnerabilities. We evaluate our approach on 442 contracts collected from CVE reports and 104 contracts with Ether leakage and suicide defects. The experimental results show that our approach reaches an average 2x speedup comparing to Mythril.

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.

This paper studies an unmanned aerial vehicle (UAV)-enabled wireless power communication networks (WPCN-s), where the UAV provides energy for mobile user nodes (M-UNs) and receives information from M-UNs. The movement of M-UN complies with a Gauss-Markov random model. To ensure acceptable quality-of-service (QoS), we consider dynamically planning the flight path of the UAV according to the movements of M-UNs. Since the flight time of UAV is restricted by limited energy, nonorthogonal multiple access (NOMA) is adopted to access a large number of M-UNs for simultaneous information transmission. Based on the above considerations, we aim to maximize the throughput via path planning of the UAV, subject to the QoS requirements of M-UNs and the UAV's energy constraint. To handle the challenges brought by dynamically changing channels to solving the problem, we propose a QoS-based double deep Q-learning network (DDQN). Numerical simulation results show that, compared with the conventional algorithms, the proposed framework achieves higher throughput.

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.

Web services facilitate the efficient execution of B2B e-commerce by integrating business processes over the Internet, which needs dynamic and flexible binding of services. However, current Web service standards do not support it. A formal approach for semantic matching of service specifications based on choreographies, i.e., the behavior of Web services, is developed in this paper. It can accurately and automatically discover required services for integrating business processes. Firstly an extended deterministic finite state automaton (EDFA) is proposed by labeling state transitions using binary-tuples (input, output) rather than letters. The automata describe Web services in a more accurate way: the nodes represent states maintained by services; the state transitions represent communication activities of services. The automata depict the temporal sequences of communication activities that describe the behaviors of services. Further, the intersection of two EDFAs is defined. Finally, an algorithm for testing the emptiness of the languages accepted by EDFAs is presented and used to evaluate the compatibility of Web services