The classic clique model has properties of hereditaries and cohesiveness. Here hereditaries means a subgraph of a clique is still a clique. Counting small cliques in a graph is a fundamental operation of numerous applications. However, the clique model is often too restrictive for practical use, leading to the focus on other relaxed-cliques with properties of hereditaries and cohesiveness. To address this issue, we investigate a new problem of counting general hereditary cohesive subgraphs (HCS). All subgraphs with properties of hereditaries and cohesiveness can be called a kind of HCS. To count HCS, we propose a general framework called HCSPivot, which can be applied to count all kinds of HCS. HCSPivot can count most HCS combinatorially without explicitly listing them. Two additional noteworthy features of HCSPivot are its ability to (1) simultaneously count HCS of any size and (2) simultaneously count HCS for each node or each edge. Based on our HCSPivot framework, we propose two novel algorithms with several carefully designed pruning techniques to count s-defective cliques and s-plexes, which are two specific types of HCS. We conduct extensive experiments on 8 large real-world graphs, and the results demonstrate the high efficiency and effectiveness of our solutions.

Some robust point cloud registration approaches with controllable pose refinement magnitude, such as ICP and its variants, are commonly used to improve 6D pose estimation accuracy. However, the effectiveness of these methods gradually diminishes with the advancement of deep learning techniques and the enhancement of initial pose accuracy, primarily due to their lack of specific design for pose refinement. In this paper, we propose Point Cloud Completion and Keypoint Refinement with Fusion Data (PCKRF), a new pose refinement pipeline for 6D pose estimation. The pipeline consists of two steps. First, it completes the input point clouds via a novel pose-sensitive point completion network. The network uses both local and global features with pose information during point completion. Then, it registers the completed object point cloud with the corresponding target point cloud by our proposed Color supported Iterative KeyPoint (CIKP) method. The CIKP method introduces color information into registration and registers a point cloud around each keypoint to increase stability. The PCKRF pipeline can be integrated with existing popular 6D pose estimation methods, such as the full flow bidirectional fusion network, to further improve their pose estimation accuracy. Experiments demonstrate that our method exhibits superior stability compared to existing approaches when optimizing initial poses with relatively high precision. Notably, the results indicate that our method effectively complements most existing pose estimation techniques, leading to improved performance in most cases. Furthermore, our method achieves promising results even in challenging scenarios involving textureless and symmetrical objects.

We propose a novel method, LoLep, which regresses Locally-Learned planes from a single RGB image to represent scenes accurately, thus generating better novel views. Without the depth information, regressing appropriate plane locations is a challenging problem. To solve this issue, we pre-partition the disparity space into bins and design a disparity sampler to regress local offsets for multiple planes in each bin. However, only using such a sampler makes the network not convergent; we further propose two optimizing strategies that combine with different disparity distributions of datasets and propose an occlusion-aware reprojection loss as a simple yet effective geometric supervision technique. We also introduce a self-attention mechanism to improve occlusion inference and present a Block-Sampling Self-Attention (BS-SA) module to address the problem of applying self-attention to large feature maps. We demonstrate the effectiveness of our approach and generate state-of-the-art results on different datasets. Compared to MINE, our approach has an LPIPS reduction of 4.8%∼9.0% and an RV reduction of 74.9% ~ 83.5%. We also evaluate the performance on real-world images and demonstrate the benefits.

We present a novel self-supervised algorithm named MotionHint for monocular visual odometry (VO) that takes motion constraints into account. A key aspect of our approach is to use an appropriate motion model that can help existing self-supervised monocular VO (SSM-VO) algorithms to overcome issues related to the local minima within their self-supervised loss functions. The motion model is expressed with a neural network named PPnet. It is trained to coarsely predict the next pose of the camera and the uncertainty of this prediction. Our self-supervised approach combines the original loss and the motion loss, which is the weighted difference between the prediction and the generated ego-motion. Taking two existing SSM-VO systems as our baseline, we evaluate our MotionHint algorithm on the standard KITTI benchmark. Experimental results show that our MotionHint algorithm can be easily applied to existing open-sourced state-of-the-art SSM-VO systems to greatly improve the performance by reducing the resulting ATE by up to 28.73%.

ROS is popular in robotic-software development, and thus detecting bugs in ROS programs is important for modern robots. Fuzzing is a promising technique of runtime testing. But existing fuzzing approaches are limited in testing ROS programs, due to neglecting ROS properties, such as multi-dimensional inputs, temporal features of inputs and the distributed node model. In this paper, we develop a new fuzzing framework named ROZZ, to effectively test ROS programs and detect bugs based on ROS properties. ROZZ has three key techniques: (1) a multi-dimensional generation method to generate test cases of ROS programs from multiple dimensions, including user data, configuration parameters and sensor messages; (2) a distributed branch coverage to describe the overall code coverage of multiple ROS nodes in the robot task; (3) a temporal mutation strategy to generate test cases with temporal information. We evaluate ROZZ on 10 common robotic programs in ROS2, and it finds 43 real bugs. 20 of these bugs have been confirmed and fixed by related ROS developers. We compare ROZZ to existing approaches for testing robotic programs, and ROZZ finds more bugs with higher code coverage.

Communication between robots and the server is a major problem for cloud robotic systems. In this paper, we address the problem caused by data loss during such communications and propose an efficient buffering algorithm, called AFR, to solve the problem. We model the problem into an optimization problem to maximize the received Quantity of Information (QoI). Our AFR algorithm is formally proved to achieve near-optimal QoI, which has a lower bound that is a constant multiple of the unrealizable optimal QoI. We implement our AFR algorithm in ROS without changing the API for the applications. Our experiments on two cloud robot applications show that our AFR algorithm can efficiently and effectively reduce the impact of data loss. For the remote mapping application, the RMSE caused by data loss can be reduced by about 20%. For the remote tracking application, the probability of tracking failure caused by data loss can be reduced from about 40 %-60 % to under 10%. Meanwhile, our AFR algorithm introduces time overhead of under 10 microseconds.

In recent years, ROS becomes the dominant middleware for robotic systems. The performance of its message-passing paradigm is crucial to the robot's reaction time. However, previous works only focus on efficiency, but ignore the requirement for transparency. We present ROS-SF framework, which can transparently eliminate serialization and de-serialization under the ROS APIs. The key contributions are a new serialization format called SFM and a life-cycle management method for serialization-free messages. Evaluation results show that our ROS-SF framework can improve the message-passing performance of ROS by up to 76.3\%. Application case study and applicability study show that our ROS-SF framework can be transparently applied to many existing ROS-based systems and packages. Even in the failure cases, our ROS-SF framework can provide modification guidance.

The data loss caused by unreliable network seriously impacts the results of remote visual SLAM systems. From our experiment, a loss of less than 1 second of data can cause a visual SLAM algorithm to lose tracking. We present a novel buffering method, ORBBuf, to reduce the impact of data loss on remote visual SLAM systems. We model the buffering problem as an optimization problem by introducing a similarity metric between frames. To solve the buffering problem, we present an efficient greedy algorithm to discard the frames that have the least impact on the quality of SLAM results. We implement our ORBBuf method on ROS, a widely used middleware framework. Through an extensive evaluation on real-world scenarios and tens of gigabytes of datasets, we demonstrate that our ORBBuf method can be applied to different state-estimation algorithms (DSO and VINS-Fusion), different sensor data (both monocular images and stereo images), different scenes (both indoor and outdoor), and different network environments (both WiFi networks and 4G networks). Our experimental results indicate that the network losses indeed affect the SLAM results, and our ORBBuf method can reduce the RMSE up to 50 times comparing with the Drop-Oldest and Random buffering methods.

Inter-process communication (IPC) is one of the core functions of modern robotics middleware. We propose an efficient IPC technique called TZC (Towards Zero-Copy). As a core component of TZC, we design a novel algorithm called partial serialization. Our formulation can generate messages that can be divided into two parts. During message transmission, one part is transmitted through a socket and the other part uses shared memory. The part within shared memory is never copied or serialized during its lifetime. We have integrated TZC with ROS and ROS2 and find that TZC can be easily combined with current open-source platforms. By using TZC, the overhead of IPC remains constant when the message size grows. In particular, when the message size is 4MB (less than the size of a full HD image), TZC can reduce the overhead of ROS IPC from tens of milliseconds to hundreds of microseconds and can reduce the overhead of ROS2 IPC from hundreds of milliseconds to less than 1 millisecond. We also demonstrate the benefits of TZC by integrating it with TurtleBot2 to be used in autonomous driving scenarios. We show that by using TZC, the braking distance can be 16% shorter than with ROS.

Modern shell scripts provide interfaces with rich functionality for system administration. However, it is not easy for end-users to write correct shell scripts; misusing commands may cause unpredictable results. In this paper, we present SmartShell, an automated function-based tool for shell script synthesis, which uses natural language descriptions as input. It can help the computer system to “understand” users’ intentions. SmartShell is based on two insights: (1) natural language descriptions for system objects (such as files and processes) and operations can be recognized by natural language processing tools; (2) system-administration tasks are often completed by short shell scripts that can be automatically synthesized from natural language descriptions. SmartShell synthesizes shell scripts in three steps: (1) using natural language processing tools to convert the description of a system-administration task into a syntax tree; (2) using program-synthesis techniques to construct a SmartShell intermediate-language script from the syntax tree; (3) translating the intermediate-language script into a shell script. Experimental results show that SmartShell can successfully synthesize 53.7% of tasks collected from shell-script helping forums.

Shared memory provides the fastest form of inter-process communication. Sharing polymorphic objects between different address spaces requires solving the issue of sharing pointers. In this paper, we propose a method, named Indexed Virtual Tables (IVT for short), to share polymorphic objects efficiently. On object construction, the virtual table pointers are replaced with indexes, which are used to find the actual virtual table pointers on dynamic dispatch. Only a few addition and load instructions are needed for both operations. Experimental results show that the IVT can outperform prior techniques on both object construction time and dynamic dispatch time. We also apply the proposed IVT technique to several practical scenarios, resulting the improvement of overall performance.

Original device drivers are often passive in common operating systems, and they should correctly handle synchronization when concurrently invoked by multiple external threads. However, many concurrency bugs have occurred in drivers due to incautious synchronization. To solve concurrency problems, active driver is proposed to replace original passive driver. An active driver has its own thread and does not need to handle synchronization, thus the occurrence probability of many concurrency bugs can be effectively reduced. But previous approaches of active driver have some limitations. The biggest limitation is that original passive driver code needs to be manually rewritten. In this paper, we propose a practical approach, AutoPA, to automatically generate efficient active driver from original passive driver code. AutoPA uses function analysis and code instrumentation to perform automated driver generation, and it uses an improved active driver architecture to reduce performance degradation. We have evaluated AutoPA on 20 Linux drivers. The results show that AutoPA can automatically and successfully generate usable active drivers from original driver code. And generated active drivers can work normally with or without the synchronization primitives in original driver code. To check the effect of AutoPA on driver reliability, we perform fault injection testing on the generated active drivers, and find that all injected concurrency faults are well tolerated and the drivers can work normally. And the performance of generated active drivers is not obviously degraded compared to original passive drivers.

Privacy inference attacks based on sensor data is an emerging and severe threat on smart devices, in which malicious applications leverage data from innocuous sensors to infer sensitive information of user, e.g., utilizing accelerometers to infer user’s keystroke. In this paper, we present Sensor Guardian, a privacy protection system that mitigates this threat on Android by hooking and controlling applications’ access to sensors. Sensor Guardian inserts hooks into applications by statically instrumenting their APK (short for Android Package Kit) files and enforces control policies in these hooks at runtime. Our evaluation shows that Sensor Guardian can effectively and efficiently mitigate the privacy inference threat on Android sensors, with negligible overhead during both static instrumentation and runtime control.

Device drivers often suffer from much more bugs than the kernel, so testing device drivers becomes more and more important and necessary. In software testing, runtime tracing is an important technique to monitor real executing procedures of the program. Meanwhile, runtime information can also assist the programmer to make more accurate analysis of the program, like verifying the correctness of code execution and detecting bugs. However, due to kernel-mode execution and high complexity of kernel code, completely tracing drivers is hard, which causes real execution paths can not be clearly identified. In order to provide more powerful support for software testing of device drivers, we propose a method named Driver Trace, to do complete runtime tracing at the function level. Driver Trace utilizes instrumentation technique for runtime tracing, which is implemented based on LLVM compiler infrastructure. When the target driver works, Driver Trace records complete runtime information of function calls, like function names, return values and parameter pointers, and the information is recorded in a log file for future analysis. We have successfully implemented Driver Trace on 10 real device drivers in Linux 3.16.4 and made the evaluation as well. The experimental results show that Driver Trace provides an effective method of runtime tracing for device drivers with the modest overhead. Moreover, using an automated analysis of the runtime information recorded by Driver Trace, we also find 6 violations about resource usages in these 10 device drivers.

Drivers use kernel extension functions to manage devices, and there are often many rules on how they should be used. Among the rules, utilization of paired functions, which means that the functions must be called in pairs between two different functions, is extremely complex and important. However, such pairing rules are not well documented, and these rules can be easily violated by programmers when they unconsciously ignore or forget about them. Therefore it is useful to develop a tool to automatically extract paired functions in the kernel source and detect incorrect usages. We put forward a method called PairMiner in this paper. Heuristic and statistical mechanisms are adopted to associate with the special structure of drivers’ source code, to find out paired functions between relative operations, and then to detect violations with extracted paired functions. In the experiment evaluation, we have successfully found 1023 paired functions in Linux 3.10.10. The utility of PairMiner was evaluated by analyzing the source code of Linux 2.6.38 and 3.10.10. PairMiner located 265 bugs about paired function violations in 2.6.38 which have been fixed in 3.10.10. We also have identified 1994 paired function violations which have not yet been fixed in 3.10.10. We have reported some violations as potential bugs with emails to the developers, 27 developers have replied the emails and 20 bugs have been confirmed so far, 2 violations are confirmed as false positive.

Device drivers require system resources to control hardware and provide fundamental services for applications. The acquired resources must be explicitly released by drivers. Otherwise, these resources will never be reclaimed by the operating system, and they are not available for other programs any more, causing hard-to-find system problems. We study on Linux driver mailing lists, and find many applied patches handle improper resource-release operations, especially in error handling paths. In order to improve current resource management and avoid resource-release omissions in device drivers, we propose a novel approach named AutoRR, which can automatically and safely release resources based on specification-mining techniques. During execution, we maintain a resource-state table by recording the runtime information of function calls. If the driver fails to release acquired resources during execution, AutoRR will report violations and call corresponding releasing functions with the recorded runtime information to release acquired resources. To fully and safely release acquired resources, a dynamic analysis of resource dependency and allocation hierarchy is also performed, which can avoid dead resources and double frees. AutoRR works in both normal execution and error handling paths for reliable resource management. We implement AutoRR with LLVM, and evaluate it on 8 Ethernet drivers in Linux 3.17.2. The evaluation shows that the overhead of AutoRR is very low, and it has successfully fixed 18 detected resource-release omission violations without side effects. Our work shows a feasible way of using specification-mining results to avoid related violations.

Device drivers usually invoke functions to allocate resources for managing hardware devices and communicating with the kernel, and these resources should be released by functions when the work is finished. Thus allocating functions and releasing functions must be invoked in pairs. However, many developers ignore this vital rule, and some allocated resources are not released in time, which may cause resource related problems like deadlocks and memory leak. For improving the resource management of device drivers, we propose an approach named Pair Dyn to check these paired functions during runtime. When the driver runs, Pair Dyn records the runtime information of allocating functions such as key parameters and return value, and dynamically detects whether the relevant releasing functions are invoked to free allocated resources during runtime. Before the driver exits, Pair Dyn automatically attempts to invoke the related releasing functions which are lacked in runtime, in order to free the allocated resources of the operation system. We have implemented Pair Dyn with the LLVM compiler infrastructure, and make the evaluation with four real device drivers in Linux version 3.10.1. The experimental result shows that with the low extra overhead, Pair Dyn can provide effective runtime checking for allocate-release paired functions. Moreover, 9 potential bugs are found in the four drivers, which are all fixed automatically before exiting. Finally, no manual modification of the source code is needed with Pair Dyn.

Kernel extension functions are provided as interfaces for drivers to manage devices and resources, and there are many implicit rules about their usages. One of the most important rules is that many functions should be called in pairs. That is to say, when an error occurs in a function, the driver should call related functions to handle it and release the acquired resources before returning, and we name these functions between normal execution paths and error handling paths as paired functions. However, many developers are unaware of them, which causes lots of bugs. Therefore, it is highly significant to automatically extract paired functions and detect violations for drivers. This paper proposes an efficient tool named BP-Miner, which can extract paired functions from binary code of driver modules and detect violations for error handling in drivers with extracted paired functions. BP-Miner constructs control flow graph (CFG) based on basic blocks of binary code, and locates potential execution paths to extract paired functions. We have evaluated BP-Miner with Linux drivers 2.6.38 and 3.13.0-rc7. 76 bugs are reported by BP-Miner in 2.6.38 which have been fixed in the current latest version 3.13.0-rc7. BP-Miner spends about 90 minutes handling 3653 module files for 3.13.0-rc7, and 859 violations have been detected with 1167 extracted paired functions. As it works on the binary code, it can be utilized to check close-source drivers.

Drivers are significant components of the operating systems(OSs), and they run in kernel mode. Generally, drivers have many errors to handle, and the functions called in the normal execution paths and error handling paths are in pairs, which are named as paired functions. However, some developers do not handle the errors completely as they forget about or are unaware of releasing the acquired resources, thus memory leaks and other potential problems can be easily introduced. Therefore, it is highly valuable to automatically extract paired functions for these problems and detect violations for the programmers. This paper proposes an efficient tool named PF-Miner, which can automatically extract paired functions and detect violations between normal execution paths and error handling paths from the source code of C program with the data mining and statistical methods. We have evaluated PF-Miner on different versions of Android kernel 2.6.39 and 3.10.0, and 81 bugs reported by PF-Miner in 2.6.39 have been fixed before the latest version 3.10.0. PF-Miner only needs about 150 seconds to analyze the source code of 3.10.0, and 983 violations have been detected from 546 paired functions that have been extracted. We have reported the top 51 violations as potential bugs to the developers, and 15 bugs have been confirmed.

Recently, internal buffer module and multi-level parallel components have already become the standard elements of SSDs. The internal buffer module is always used as a write cache, reducing the erasures and thus improving overall performance. The multi-level parallelism is exploited to service requests in a concurrent or interleaving manner, which promotes the system throughput. These two aspects have been extensively discussed in the literature. However, current buffer algorithms cannot take full advantage of parallelism inside SSDs. In this paper, we propose a novel write buffer management scheme called Parallelism-Aware Buffer (PAB). In this scheme, the buffer is divided into two parts named as Work-Zone and Para-Zone respectively. Conventional buffer algorithms are employed in the Work-Zone, while the Para-Zone is responsible for reorganizing the requests evicted from Work-Zone according to the underlying parallelism. Simulation results show that with only a small size of Para-Zone, PAB can achieve 19.2% ~ 68.1% enhanced performance compared with LRU based on a page-mapping FTL, while this improvement scope becomes 5.6% ~ 35.6% compared with BPLRU based on the state-of-the-art block-mapping FTL known as FAST.

Reducing disk energy consumption and improving disk performance in high-performance computer systems are increasingly pressing issues for reasons of disk economy and efficiency. To achieve these goals, we define the concept of Immediate Successor Relationship Amount (ISRA) to represent the successor relationship of data blocks, and propose an ISRA-based grouping algorithm for disk reorganization, based on an undirected graph. We group data blocks that experience frequent successive accesses, then sort them using a merge-sort-like algorithm to determine the position of every group as well as the new position of every block within those groups. We evaluate our approach in terms of disk seek time and disk energy consumption, using Disksim and the log energy model. The results show clearly that both disk seek time and the energy needs can be reduced by about 50 percent.

In this paper, we propose a new semi-fragile watermarking algorithm for the authentication of 3D models based on integral invariants. A watermark image is embedded by modifying the integral invariants of some of the vertices. In order to modify the integral invariants, the positions of a vertex and its neighbors are shifted. To extract the watermark, all the vertices are tested for the embedded information, and this information is combined to recover the watermark image. The number of parts of the watermark image that can be recovered will determine the authentication decision. Experimental tests show that this method is robust against normal use modifications introduced by rigid transformations, format conversions, rounding errors, etc., and can be used to test for malicious attacks such as mesh editing and cropping. An additional contribution of this paper is a new algorithm for computing two kinds of integral invariants.