Abstract The principled combination of symbolic execution and random testing lacks a formal foundation, especially in deciding which inputs to symbolize. We propose selective concolic testing, a cost-aware framework that formulates this choice as an optimized policy problem of a MDP (Markov Decision Process). We model program exploration over a finite control-flow graph, where MDP states represent covered statements, actions partition path constraints into symbolic and random fragments, rewards reflect coverage gain, and costs account for SMT solving effort and sampling inefficiency. Our framework yields the first formal characterization of selective symbolization as policy synthesis in a probabilistic system. We prove that exact policy computation is intractable due to the exponential state space and the hardness of solution-density estimation via model counting. Our formulation enables a practical approximation: we partition constraint dependency graphs and use machine learning to predict solver timeouts, guiding per-constraint symbolization decisions. Built on top of KLEE and JFS, our prototype validates the approach on real-world floating-point benchmarks. Results show that selectively symbolizing inputs, guided by predicted solvability and cost, significantly improves coverage efficiency. Our work thus provides both a rigorous theoretical foundation and a practical instantiation for hybrid program analysis.

Backward-compatible training enables the deployment of advanced models without requiring updates to old gallery databases. However, existing methods, including old-prototype-based (i.e., those relying on prototypes from the old model) and instance-based approaches, often overlook the impact of the old model's quality. High-quality old models exhibit compact intra-class feature distributions, which facilitate effective alignment between old and new models across various methods. In contrast, low-quality old models produce dispersed features, making it difficult for old-prototype-based methods to extract sufficient information. Additionally, instance-based methods are overly restrictive, limiting the flexibility of new models. In this work, we propose SA-BCT, an extremely simple yet effective backward-compatible training method that offers a unified framework for accommodating old models of varying quality. SA-BCT employs a single loss function applied to both old and new features, self-adaptively adjusting the constraint space for new features based on the distribution of old features. Extensive experiments in diverse settings demonstrate the effectiveness of SA-BCT. Code is available athttps://github.com/yuleung/SA-BCT.

Fuzzing is an efficient automated testing technique for discovering vulnerabilities. It generates and feeds random or pseudo-random data to the target system, aiming to trigger potential bugs or anomalous behaviors that can not be revealed by normal tests designed by system developers. A critical factor in mutation-based fuzzing is seed selection strategy, i.e., how to choose the most promising seed to mutate. Existing seed selection strategies are mostly static and lack the capability to dynamically adjust according to the specific characteristics of different target programs. To address this limitation, we propose a dynamic seed selection strategy based on machine learning techniques. Our method utilizes seed features obtained statically or dynamically to prioritize seeds via a scoring model. The scoring model is trained during the fuzzing process to suit the current target program. Consequently, we can obtain a dynamic seed selection strategy that varies across different programs, and hence enhance the efficiency of fuzzing process. In addition, we use entropy-based power scheduling to improve the performance of fuzzing further. Experimental results on real-world programs demonstrate that our method outperforms the state-of-the-art seed selection method and improves the efficiency of fuzzing especially in the number of discovered unique crashes.

With the advancement of satellite computing capabilities, the diversity of satellite communication services imposes varied quality of service (QoS) requirements. Limited satellite resources necessitate remote deployment and updates of running services for QoS testing, increasing testing difficulty. Existing testing tools are limited in functionality or reliant on specific infrastructures, failing to meet the QoS testing needs of edge cloud services in mobile satellite scenarios. In this paper, we present SECTest, an integrated testing platform for QoS in satellite edge clouds. More precisely, SECTest can integrate changes in satellite network topology, create and manage satellite edge cloud cluster testing environments on heterogeneous edge devices, customize experiments for users, support deployment and scaling of various integrated testing tools, provide test data persistence function to manage data life cycle and store data hierarchically, and publish and visualize test results. We have built a real satellite edge cloud cluster based on Kubernetes, integrating both physical and virtual machines, and deploying a variety of integrated testing tools using containerization technology. Currently, we have evaluated the quality of service in terms of processing latency, packet drop rate, throughput, and average response time for object detection microservice applications, web microservice applications, and data transfer tasks. To demonstrate SECTest's scalability in testing network communication protocols, we evaluated the performance of HTTP and gRPC in microservice communication within the cluster. Our experimental results validate SECTest's ability to test key service quality metrics in a real satellite edge cloud cluster.

The goal of the Single-Row Facility Layout Problem (SRFLP) is to arrange facilities along a straight line in such a way that the total layout cost is minimized. This cost is calculated as the sum of the products of flow costs and the distances between pairs of facilities. SRFLP has numerous practical applications in real-life scenarios, but it is NP-hard. To solve the Single-Row Facility Layout Problem (SRFLP), we propose a novel solution method SRFL-DP. This approach models SRFLP as an electrostatic equilibrium problem, enabling the derivation of a feasible solution in a very short time. Then, a simulated annealing algorithm is applied to this feasible solution, allowing for the exchange of facilities to further reduce the total layout cost. Our method significantly reduces the computational time required to obtain results. When compared with the state-of-the-art KMPG algorithm on the Ranlarge dataset with 2000 facilities, our method takes only 1/11th of the time and performs even faster on other datasets.

The diversification of satellite communication services imposes varied requirements on network service quality, making quality of service (QoS) testing for microservices running on satellites more complex. Existing testing tools have limitations, potentially offering only single-functionality testing, thus failing to meet the requirements of QoS testing for edge cloud services in mobile satellite scenarios. In this paper, we propose a framework for integrating quality of service testing in satellite edge clouds. More precisely, the framework can integrate changes in satellite network topology, create and manage satellite edge cloud cluster testing environments on heterogeneous edge devices, customize experiments for users, support deployment and scaling of various integrated testing tools, and publish and visualize test results. Our experimental results validate the framework’s ability to test key service quality metrics in a satellite edge cloud cluster.

Message-passing programs involve several processes with channel-based communications to deal with tasks concurrently. The complex computations and communications between processes make the verification of message-passing programs hard. By regarding the functions in programs as uninterpreted functions, we focus on the verification problem of message-passing uninterpreted programs. Although the usage of uninterpreted functions alleviates the computational difficulties brought by functions, the verification problem is still undecidable in general. In this work, we provide a decidable subclass of message-passing uninterpreted programs, wherein programs in this subclass satisfy the property of k-record coherence . The decidability result closely relies on communicating finite-state machine (CFM) with bounded channels. Based on the decidability result, we proposed a verification framework for message-passing uninterpreted programs.

Summary Constraint solving is the enabling technique for symbolic execution. The advancement of constraint solving boosts the development and application of symbolic execution. Modern Satisfiability Modulo Theories (SMT) solvers provide the mechanism of solving strategy, allowing users to control the solving procedure. This mechanism significantly improves the solver's generalization ability. We observe that the symbolic executions of different programs are different constraint solving problems. Therefore, we propose synthesizing solving strategies for a program to fit the program's symbolic execution best. To achieve this, we propose an adaptive framework for synthesizing solving strategies, in which the constraints are classified into different categories, and the solving strategies are synthesized for different categories on demand. We propose novel synthesis algorithms that combine the offline trained deep learning models and online tuning to synthesize the solving strategy. The algorithms balance the synthesis overhead and the improvement achieved by the synthesized solving strategy. We have implemented our method on the state‐of‐the‐art symbolic execution engine KLEE for C programs and Symbolic Pathfinder (SPF) for Java programs. The results of the extensive experiments indicate that our method effectively improves the efficiency of symbolic execution. For the Coreutils benchmark, our method, on average, increases the numbers of paths and queries by 74.37% and 73.94% under Breadth First Search (BFS), respectively. Besides, we applied our method to a different benchmark of C programs and a benchmark of Java programs to validate the generalization ability. The results demonstrate that for the C benchmark, our method increases the numbers of paths and queries by 71.09% and 70.60% under BFS, respectively; For the Java benchmark, our method increases the numbers of paths and queries by 50.31% and 49.93% under BFS, respectively. These results show that our method has a good generalization ability.

Recent research has revealed that deep generative models including flow-based models and Variational Autoencoders may assign higher likelihoods to out-of-distribution (OOD) data than in-distribution (ID) data. However, we cannot sample OOD data from the model. This counterintuitive phenomenon has not been satisfactorily explained and brings obstacles to OOD detection with flow-based models. In this article, we prove theorems to investigate the Kullback-Leibler divergence in flow-based model and give two explanations for the above phenomenon. Based on our theoretical analysis, we propose a new method KLODS to leverage KL divergence and local pixel dependence of representations to perform anomaly detection. Experimental results on prevalent benchmarks demonstrate the effectiveness and robustness of our method. For group anomaly detection, our method achieves 98.1% AUROC on average with a small batch size of 5. On the contrary, the baseline typicality test-based method only achieves 64.6% AUROC on average due to its failure on challenging problems. Our method also outperforms the state-of-the-art method by 9.1% AUROC. For point-wise anomaly detection, our method achieves 90.7% AUROC on average and outperforms the baseline by 5.2% AUROC. Besides, our method has the least notable failures and is the most robust one.

Message-passing interface (MPI) programs are non-deterministic and challenging to ensure correctness. The introduction of one-sided communications makes the problem of non-determinism more severe for MPI programs. This paper reports our in-progress work of symbolic execution for the MPI programs with one-sided communications. Our approach can cover the non-determinism caused by the inputs, one-sided communication, and message- passing operations of MPI programs. The preliminary evaluation's results indicate the promising of our approach.

Constraint solving stands out as a significant bot-tleneck in symbolic execution. Caching is a commonly adopted approach to alleviate this bottleneck. However, the cutting-edge caching technique targeting unsatisfiable constraints, known as unsatisfiable core caching, primarily involves checking whether the constraint being solved contains an unsatisfiable core that has been previously collected. Such straightforward reuse frequently proves less effective in numerous scenarios. In this paper, we present a novel method to enhance the utilization of unsatisfiable cores. By excavating unsatisfiable cores, our method can compute an easily solvable over-approximation that tends to be unsatis-fiable for each constraint, which facilitates the determination of the satisfiability of the original constraint. We implemented our method on KLEE symbolic executor. The evaluation results on 27 real-world programs are encouraging.

Kullback-Leibler (KL) divergence is one of the most important measures to calculate the difference between probability distributions. In this paper, we theoretically study several properties of KL divergence between multivariate Gaussian distributions. Firstly, for any two $n$-dimensional Gaussian distributions $\mathcal{N}_1$ and $\mathcal{N}_2$, we prove that when $KL(\mathcal{N}_2||\mathcal{N}_1)\leq \varepsilon\ (\varepsilon>0)$ the supremum of $KL(\mathcal{N}_1||\mathcal{N}_2)$ is $(1/2)\left((-W_{0}(-e^{-(1+2\varepsilon)}))^{-1}+\log(-W_{0}(-e^{-(1+2\varepsilon)})) -1 \right)$, where $W_0$ is the principal branch of Lambert $W$ function. For small $\varepsilon$, the supremum is $\varepsilon + 2\varepsilon^{1.5} + O(\varepsilon^2)$. This quantifies the approximate symmetry of small KL divergence between Gaussian distributions. We further derive the infimum of $KL(\mathcal{N}_1||\mathcal{N}_2)$ when $KL(\mathcal{N}_2||\mathcal{N}_1)\geq M\ (M>0)$. We give the conditions when the supremum and infimum can be attained. Secondly, for any three $n$-dimensional Gaussian distributions $\mathcal{N}_1$, $\mathcal{N}_2$, and $\mathcal{N}_3$, we theoretically show that an upper bound of $KL(\mathcal{N}_1||\mathcal{N}_3)$ is $3\varepsilon_1+3\varepsilon_2+2\sqrt{\varepsilon_1\varepsilon_2}+o(\varepsilon_1)+o(\varepsilon_2)$ when $KL(\mathcal{N}_1||\mathcal{N}_2)\leq \varepsilon_1$ and $KL(\mathcal{N}_2||\mathcal{N}_3)\leq \varepsilon_2$ ($\varepsilon_1,\varepsilon_2\ge 0$). This reveals that KL divergence between Gaussian distributions follows a relaxed triangle inequality. Note that, all these bounds in the theorems presented in this work are independent of the dimension $n$. Finally, we discuss several applications of our theories in deep learning, reinforcement learning, and sample complexity research.

Constraint solving and environment modeling are two challenging problems for symbolic execution. When a program contains non-linear expressions, it is difficult for symbolic execution to explore the program’s whole path space due to the high complexity of the constraint solving for the nonlinear constraints. Besides, when the program uses a third-party library and the source code of the library is not available, the symbolic execution of the program often under-approximates the analysis by concrete execution or over-approximates by introducing new symbolic variables, which may fail to explore the whole path space or introduce false alarms, respectively. This paper proposes FUSE, a framework of synergizing symbolic execution and fuzzing by function-level selective symbolization to tackle these problems. First, FUSE collects the path constraints of each function selectively and introduces symbolic function invocation expressions for the complex or third-party functions. Then, FUSE combines SMT solving and fuzzing to solve the path constraints. We have implemented FUSE on the start-of-theart symbolic execution engine KLEE. The experimental results demonstrate that FUSE effectively and efficiently improves the code coverage. Compared with the state-of-the-art, FUSE achieves 6. 6x speedups for achieving the same code coverage.

Symbolic execution is powered by constraint solving. The advancement of constraint solving boosts the development and the applications of symbolic execution. Modern SMT solvers provide the mechanism of solving strategy that allows the users to control the solving procedure, which significantly improves the solver's generalization ability. We observe that the symbolic executions of different programs are actually different constraint solving problems. Therefore, we propose synthesizing a solving strategy for a program to fit the program's symbolic execution best. To achieve this, we divide symbolic execution into two stages. The SMT formulas solved in the first stage are used to online synthesize a solving strategy, which is then employed during the constraint solving in the second stage. We propose novel synthesis algorithms that combine offline trained deep learning models and online tuning to synthesize the solving strategy. The algorithms balance the synthesis overhead and the improvement achieved by the synthesized solving strategy.

Parsing code exists extensively in software. Symbolic execution of complex parsing programs is challenging. The inputs generated by the symbolic execution using the byte-level symbolization are usually rejected by the parsing program, which dooms the effectiveness and efficiency of symbolic execution. Complex parsing programs usually adopt token-based input grammar checking. A token sequence represents one case of the input grammar. Based on this observation, we propose grammar-agnostic symbolic execution that can automatically generate token sequences to test complex parsing programs effectively and efficiently. Our method's key idea is to symbolize tokens instead of input bytes to improve the efficiency of symbolic execution. Technically, we propose a novel two-stage algorithm: the first stage collects the byte-level constraints of token values; the second stage employs token symbolization and the constraints collected in the first stage to generate the program inputs that are more possible to pass the parsing code.

Array constraints are prevalent in analyzing a program with symbolic execution. Solving array constraints is challenging due to the complexity of the precise encoding for arrays. In this work, we propose to synergize symbolic execution and array constraint solving. Our method addresses the difficulties in solving array constraints with novel ideas. First, we propose a lightweight method for pre-checking the unsatisfiability of array constraints based on integer linear programming. Second, observing that encoding arrays at the byte-level introduces many redundant axioms that reduce the effectiveness of constraint solving, we propose type and interval aware axiom generation. Note that the type information of array variables is inferred by symbolic execution, whereas interval information is calculated through the above pre-checking step. We have implemented our methods based on KLEE and its underlying constraint solver STP and conducted large-scale experiments on 75 real-world programs. The experimental results show that our method effectively improves the efficiency of symbolic execution. Our method solves 182.56% more constraints and explores 277.56% more paths on average under the same time threshold.

Constraint solving is one of the challenges for symbolic execution. Modern SMT solvers allow users to customize the internal solving procedure by solving strategies. In this extended abstract, we report our recent progress in synthesizing a program-specific solving strategy for the symbolic execution of a program. We propose a two-stage procedure for symbolic execution. At the first stage, we synthesize a solving strategy by utilizing deep learning techniques. Then, the strategy will be used in the second stage to improve the performance of constraint solving. The preliminary experimental results indicate the promising of our method.

Path explosion and constraint solving are two challenges to symbolic execution's scalability. Symbolic execution explores the program's path space with a searching strategy and invokes the underlying constraint solver in a black-box manner to check the feasibility of a path. Inside the constraint solver, another searching procedure is employed to prove or disprove the feasibility. Hence, there exists the problem of double searchings in symbolic execution. In this paper, we propose to unify the double searching procedures to improve the scalability of symbolic execution. We propose Multiplex Symbolic Execution (MuSE) that utilizes the intermediate assignments during the constraint solving procedure to generate new program inputs. MuSE maps the constraint solving procedure to the path exploration in symbolic execution and explores multiple paths in one time of solving. We have implemented MuSE on two symbolic execution tools (based on KLEE and JPF) and three commonly used constraint solving algorithms. The results of the extensive experiments on real-world benchmarks indicate that MuSE has orders of magnitude speedup to achieve the same coverage.

Symbolic execution is still facing the scalability problem caused by path explosion and constraint solving overhead. The recently proposed MuSE framework supports exploring multiple paths by generating partial solutions in one time of solving. In this work, we improve MuSE from two aspects. Firstly, we use a light-weight check to reduce redundant partial solutions for avoiding the redundant executions having the same results. Secondly, we introduce online learning to devise an adaptive search strategy for the target programs. The preliminary experimental results indicate the promising of the proposed methods.

It is challenging to effectively check a regular property of a program. This paper presents RGSE, a regular property guided dynamic symbolic execution (DSE) engine, for finding a program path satisfying a regular property as soon as possible. The key idea is to evaluate the candidate branches based on the history and future information, and explore the branches along which the paths are more likely to satisfy the property in priority. We have applied RGSE to 16 real-world open source Java programs, totaling 270K lines of code. Compared with the state-of-the-art, RGSE achieves two orders of magnitude speedups for finding the first target path. RGSE can benefit many research topics of software testing and analysis, such as path-oriented test case generation, typestate bug finding, and performance tuning. The demo video is at: https://youtu.be/7zAhvRIdaUU, and RGSE can be accessed at: http://jrgse.github.io.

A challenging problem in software engineering is to check if a program has an execution path satisfying a regular property. We propose a novel method of dynamic symbolic execution (DSE) to automatically find a path of a program satisfying a regular property. What makes our method distinct is when exploring the path space, DSE is guided by the synergy of static analysis and dynamic analysis to find a target path as soon as possible. We have implemented our guided DSE method for Java programs based on JPF and WALA, and applied it to 13 real-world open source Java programs, a total of 225K lines of code, for extensive experiments. The results show the effectiveness, efficiency, feasibility and scalability of the method. Compared with the pure DSE on the time to find the first target path, the average speedup of the guided DSE is more than 258X when analyzing the programs that have more than 100 paths.

Symbolic execution is an effective path oriented and constraint based program analysis technique. Recently, there is a significant development in the research and application of symbolic execution. However, symbolic execution still suffers from the scalability problem in practice, especially when applied to large-scale or very complex programs. In this paper, we propose a new fashion of symbolic execution, named Speculative Symbolic Execution (SSE), to speed up symbolic execution by reducing the invocation times of constraint solver. In SSE, when encountering a branch statement, the search procedure may speculatively explore the branch without regard to the feasibility. Constraint solver is invoked only when the speculated branches are accumulated to a specified number. In addition, we present a key optimization technique that enhances SSE greatly. We have implemented SSE and the optimization technique on Symbolic Pathfinder (SPF). Experimental results on six programs show that, our method can reduce the invocation times of constraint solver by 20.7% to 48.7% (with an average of 29.9%), and save the search time from 23.6% to 43.6% (with an average of 30%).

Software testers are confronted with great challenges in testing Web Services (WS) especially when integrating to services owned by other vendors. They must deal with the diversity of implementation techniques used by the other services and to meet a wide range of test requirements. However, they are in lack of software artifacts, the means of control over test executions and observation on the internal behavior of the other services. An automated testing technique must be developed to be capable of testing on-the-fly nonintrusively and nondisruptively. Addressing these problems, this paper proposes a framework of collaborative testing in which test tasks are completed through the collaboration of various test services that are registered, discovered, and invoked at runtime using the ontology of software testing STOWS. The composition of test services is realized by using test brokers, which are also test services but specialized in the coordination of other test services. The ontology can be extended and updated through an ontology management service so that it can support a wide open range of test activities, methods, techniques, and types of software artifacts. The paper presents a prototype implementation of the framework in semantic WS and demonstrates the feasibility of the framework by running examples of building a testing tool as a test service, developing a service for test executions of a WS, and composing existing test services for more complicated testing tasks. Experimental evaluation of the framework has also demonstrated its scalability.

This paper proposes an intelligent broker approach to service composition and collaboration. The broker employs a planner to generate service composition plans according to service usage and workflow knowledge, dynamically searches for services according to the plan, then invokes and coordinates the executions of the selected services at runtime. A prototype called I-Broker has been implemented to support the approach, which can be instantiated by populating the knowledge-base with domain specific knowledge to form domain specific brokers. This paper also reports experiments that evaluate the scalability of the approach.

This paper presents a method of component testing based on algebraic specifications. An algorithm for generating checkable test cases is proposed. A prototype testing tool called CASCAT for testing Java Enterprise Beans is developed. It has the advantages of high degree of automation, which include test case generation, test harness construction and test result checking. It achieves scalability by allowing incremental integration. It also allows testing to focus on a subset of used functions and key properties, thus suitable for component testing. The paper also reports an experimental evaluation of the method and the tool.