AL-SMC: Optimizing Statistical Model Checking by Automatic Abstraction and Learning

Statistical Model Checking (SMC), as a technique to mitigate the issue of state space explosion in numerical probabilistic model checking, can efficiently obtain an approximate result with an error bound by statistically analysing the simulation traces. SMC however may become very time consuming due to the generation of an extremely large number of traces in some cases. Improving the performance of SMC effectively is still a challenge. To solve the problem, we propose an optimized SMC approach called AL-SMC which effectively reduces the required sample traces, thus to improve the performance of SMC by automatic abstraction and learning. First, we present property-based trace abstraction for simplifying the cumbersome traces drawn from the original model. Second, we learn the analysis model called Prefix Frequency Tree (PFT) from the abstracted traces, and optimize the PFT using the two-phase reduction algorithm. By means of the optimized PFT, the original probability space is partitioned into several sub-spaces on which we evaluate the probabilities parallelly in the final phase. Besides, we analyse the core algorithms in terms of time and space complexity, and implement AL-SMC in our Modana Platform to support the automatic process. Finally we discuss the experiment results for the case study :energy-aware building which shows that the number of sample traces is effectively reduced (by nearly 20\% to 50\%) while ensuring the accuracy of the result with an acceptable error.     

On the detection of signaling DoS attacks on 3G/WiMax wireless networks

Third generation (3G) wireless networks based on the CDMA2000 and UMTS standards are now increasingly being deployed throughout the world. Because of their complex signaling and relatively limited bandwidth, these 3G networks are generally more vulnerable than their wireline counterparts, thus making them fertile ground for new attacks. In this paper, we identify and study a novel denial of service (DoS) attack, called signaling attack, that exploits the unique vulnerabilities of the signaling/control plane in 3G wireless networks. Using simulations driven by real traces, we are able to demonstrate the impact of a signaling attack. Specifically, we show how a well-timed low-volume signaling attack can potentially overload the control plane and detrimentally affect the key elements in a 3G wireless infrastructure. The low-volume nature of the signaling attack allows it to avoid detection by existing intrusion detection algorithms, which are often signature or volume-based. As a counter-measure, we present and evaluate an online early detection algorithm based on the statistical CUSUM method. Through the use of extensive trace-driven simulations, we demonstrate that the algorithm is robust and can identify an attack in its inception, before significant damage is done. Apart from 3G networks, we also show that many emerging wide-area networks such as 802.16/WiMax share the same vulnerability and our solution can also apply.     

Using mobile node speed changes for movement direction change prediction in a realistic category of mobility models

In order to evaluate performance of protocols for ad hoc networks, the protocols have to be tested under realistic conditions. These conditions may include a reasonable transmission range, a limited buffer size, and realistic movement of mobile users (mobility models). In this paper, we propose a new and realistic type of random mobility models in which the mobile node has to decelerate to reach the point of direction change and accelerates with a defined acceleration to reach its intended speed. This realistic mobility model is proposed based on random mobility models. In reality, mobile objects tend to change their speed when they are going to change their direction, i.e. decelerate when approaching a direction change point and accelerate when they start their movement in a new direction. Therefore, in this paper, we implement this behavior in random mobility models which lack such specification. In fact, this paper represents our effort to use this accelerated movement to anticipate a probable direction change of a mobile node with reasonable confidence. The simulation type of this paper is based on traces produced by a mobility trace generator tool. We use a data mining concept called association rule mining to find any possible correlations between accelerated movement of mobile node and the probability that mobile node wants to change its direction. We calculate confidence and lift parameters for this matter, and simulate this mobility model based on random mobility models. These simulations show a meaningful correlation between occurrence of an accelerated movement and event of mobile node's direction change.     

Discovering periodic patterns of nodal encounters in mobile networks

Routing in Delay Tolerant Networks is very challenging because of frequent disconnections. One cause of disconnection is node movement. Disconnections can be overcome by finding a set of sequential opportunistic encounters between pairs of mobile nodes. These encounters can be used for message forwarding and delivery. In this context, understanding user mobile behaviour is essential to design effective and efficient network protocols. This paper presents a generic methodology to model and find periodic encounter patterns by using the auto-persistence function and detection techniques derived from it. From the studies on four real mobility traces, we are able to detect strong weekly periodic encounter patterns with an accuracy of up to 100%. The experimental results show that periodic encounter patterns in real mobility traces do not last long, e.g., years, because they are interrupted by unexpected events from time to time. Nonetheless our experimental results show that those periodic encounters can still last up to a few months. Furthermore, we show that, for some of the mobility traces, the network formed by periodic encounters forms a small-world structure.     

SCARE and power attack on AES-like block ciphers with secret S-box

Despite Kerckhoff's principle, there are secret ciphers with unknown components for diplomatic or military usages. The side-channel analysis of reverse engineering (SCARE) is developed for analyzing secret ciphers. Considering the side-channel leakage, SCARE attacks enable the recovery of some secret parts of a cryptosystem, e.g., the substitution box table. However, based on idealized leakage assumption, most of these attacks have a few limitations on prior knowledge or implementations. In this paper, we focus on AES-like block ciphers with a secret S-box and demonstrate an attack which recovers both the secret key and the secret S-box. On the one hand, the key is recovered under profiled circumstance by leakage analysis and collision attack. On the other hand, the SCARE attack is based on mathematical analysis. It relies on Hamming weight of MixColumns intermediate results in the first round, which can restore the secret S-box. Experiments are performed on real power traces from a software implementation of AES-like block cipher. Moreover, we evaluate the soundness and efficiency of our method by simulations and compare with previous approaches. Our method has more advantages in intermediate results location and the required number of traces. For simulated traces with gaussian noise, our method requires 100000 traces to fully restore the secret S-box, while the previous method requires nearly 300000 traces to restore S-box.     

Improving source routing reliability in mobile ad hoc networks

In this paper, we propose a novel on-demand routing protocol called backup source routing (BSR) to establish and maintain backup routes that can be utilized after the primary path breaks. The key advantage of BSR is the reduction of the frequency of route discovery flooding, which is recognized as a major overhead in on-demand protocols. We define a new routing metric, called the route reliability, and use it to provide the basis for the backup path selection. We use a heuristic cost function to develop an analytical model and an approximation method to measure this metric. Various algorithms for our BSR protocol in the route discovery phase and route maintenance phase have been designed based on this cost function. Extensive simulations demonstrated that our routing strategy has two interesting features: 1) in less stressful situations of lower mobility, BSR has similar performance to DSR, 2) in more challenging situations of high mobility, BSR can improve the performance significantly.     

面向未解释程序的合作验证方法

未解释程序的验证问题通常是不可判定的,但是最近有研究发现,存在一类满足coherence性质的未解释程序,其验证问题是可判定的,并且计算复杂度为PSPACE完全的.在这个结果的基础上,一个针对一般未解释程序验证的基于路径抽象的反例抽象精化（CEGAR）框架被提出,并展现了良好的验证效率.即使如此,对未解释程序的验证工作依然需要多次迭代,特别是利用该方法在针对多个程序验证时,不同的程序之间的验证过程是彼此独立的,存在验证开销巨大的问题.本文发现被验证的程序之间较为相似时,不可行路径的抽象模型可以在不同的程序之间复用.因此,本文提出了一个合作验证的框架,收集在验证过程中不可行路径的抽象模型,并在对新程序进行验证时,用已保存的抽象模型对程序进行精化,提前删减一些已验证的程序路径,从而提高验证效率.此外,本文通过对验证过程中的状态信息进行精简,对现有的基于状态等价的路径抽象方法进行优化,以进一步提升其泛化能力.本文对合作验证的框架以及路径抽象的优化方法进行了实现,并在两个具有代表性的程序集上分别取得了2.70x和1.49x的加速.     

Utilizing correlated node mobility for efficient DTN routing

In a delay tolerant network (DTN), nodes are connected intermittently and the future node connections are mostly not known. Therefore, effective forwarding based on limited knowledge of contact behavior of nodes is challenging. Most of the previous studies assumed that mobility of a node is independent from mobility of other nodes and looked at only the pairwise node relations to decide routing. In contrast, in this paper, we analyze the temporal correlation between the meetings of each node with other nodes and utilize this correlation for efficient routing. We introduce a new metric called conditional intermeeting time (CIT), which computes the average intermeeting time between two nodes relative to a meeting with a third node. Then, we modify existing DTN routing protocols using the proposed metric to improve their performance. Extensive simulations based on real and synthetic DTN traces show that the modified algorithms perform better than the original ones.     

对标准模型下无证书签名方案的安全性分析

通过对一个标准模型下可证安全的无证书签名方案进行分析,指出该方案是不安全的。分析了一种针对该方案的公钥替换攻击和改进方案,说明该公钥替换攻击是一种平凡的伪造攻击,指出了这个改进方案也是不安全的。提出了一种新的密钥生成中心KGC攻击,即通用恶意KGC攻击,在这种攻击下,这两个无证书签名方案的KGC总是能够在系统参数生成阶段生成包含陷门信息的系统参数,利用这些参数,KGC不需要计算出用户的私钥就可以冒充任意系统用户对任意消息进行伪造签名。给出了攻击方法,并针对这种通用恶意KGC攻击提出了新的改进方案,使其能够抵抗这种攻击。     

Trace-based mobility modeling for multi-hop wireless networks

Realistic and scenario-dependent mobility modeling is crucial for the reliable performance evaluation of multi-hop networks. In the last decade, a significant number of synthetic mobility models have been proposed. However, only a few of these models have been validated by realistic movement traces. In the last few years, several of such traces have been collected, analyzed, and made available to the community. This paper provides a comprehensive and up-to-date survey of (1) available movement traces, (2) modeling/analyses of these traces, and (3) synthetic mobility models. The focus of the paper is on mobility traces/models that include position information. The contribution of this paper is to summarize the research that has been done in the area of mobility modeling over the last few years and present challenges for future work.     

CAF: Community aware framework for large scale mobile opportunistic networks

The fundamental challenge in opportunistic networking is when and how to forward a message. Rank-based forwarding, one of the most promising methods for addressing this challenge, ranks nodes based on their social profiles or contact history in order to identify the most suitable forwarders. While these forwarding techniques have demonstrated great performance trends, we observe that they fail to efficiently forward messages in large scale networks. In this paper, we demonstrate using real mobility traces, the weakness of existing rank-based forwarding algorithms in large scale communities. We propose strategies for partitioning large communities into sub-communities based on geographic locality or social interests. We also propose exploiting particular nodes, named MultiHomed nodes, in order to disseminate messages across these sub-communities. We introduce CAF, a Community Aware Forwarding framework, which is designed to be integrated with state-of-the-art rank-based forwarding algorithms, in order to improve their performance in large scale networks. We use real mobility traces to evaluate our proposed techniques. Our results empirically show a delivery success rate increase of up to 40%, along with 5% to 30% improved success delivery rates compared to state-of-the-art rank-based forwarding algorithms; these results are obtained while incurring a marginal increase in cost which is less than 10%. We finally propose an extension of the original framework called Community Destination Aware Framework (CDAF). Assuming that the source node can determine the destination’s community, CDAF further reduces the cost of CAF by a factor of 2 while maintaining similar success rates.     

A method for combining odometry and distance sensor information for effective obstacle avoidance of autonomous mobile robots

In this paper, a concept for virtual sensors is proposed for efficient avoidance of obstacles during the motion of robots. The virtual sensor yields new data by combining encoder values and real distance data, and derives new sensor data that includes the mobility of the robot. Simulation on Windows XP is executed to illustrate the proposed approach with actually acquired distance from virtual and actual sensors. To facilitate comparison with the alternative results developed in this paper, we refer to the conventional artificial potential field method using actual distance. Data from virtual sensors show smoother and safer motion in obstacle avoidance traces in regards to obstacle and robot mobility.     

Modeling pedestrian mobility in disaster areas

Realistic mobility modeling is necessary for testing disaster management strategies as well as performance of disaster–resilient networks. Evacuation of the people from a disaster area depends on the environment and type of the hazard which cause certain changes in the pedestrian flows. Although most models focus on the building evacuations or city-scale evacuation planning, there is a need for a mobility model that captures the pedestrians’ movement behavior during evacuation from large and crowded disaster areas such as theme parks.In this paper, we propose a mobility model of the pedestrians in disaster areas. In our application scenario of theme parks, the main mission of the operators is the evacuation of the visitors and providing access to transportation vehicles such as ambulances. We use real maps to generate theme park models with obstacles, roads, and disaster events. We incorporate macro and micro mobility decisions of the visitors, considering their local knowledge and the social interactions among the visitors. We analyze the outcomes of the simulation of our theme park disaster (TP-D) mobility model with simulations of currently used models and real-world GPS traces. Moreover, using the proposed model as a baseline, we analyze the performance of an opportunistic network application.     

A metamodel for the compact but lossless exchange of execution traces

Understanding the behavioural aspects of a software system can be made easier if efficient tool support is provided. Lately, there has been an increase in the number of tools for analysing execution traces. These tools, however, have different formats for representing execution traces, which hinders interoperability and limits reuse and sharing of data. To allow for better synergies among trace analysis tools, it would be beneficial to develop a standard format for exchanging traces. In this paper, we present a graph-based format, called compact trace format (CTF), which we hope will lead the way towards such a standard. CTF can model traces generated from a variety of programming languages, including both object-oriented and procedural ones. CTF is built with scalability in mind to overcome the vast size of most interesting traces. Indeed, the design of CTF is based on the idea that call trees can be transformed into more compact ordered acyclic directed graphs by representing similar subtrees only once. CTF is also supported by our trace analysis tool SEAT (Software Exploration and Analysis Tool).     

A quantitative model of the security intrusion process based onattacker behavior

The paper is based on a conceptual framework in which security can be split into two generic types of characteristics, behavioral and preventive. Here, preventive security denotes the system's ability to protect itself from external attacks. One way to describe the preventive security of a system is in terms of its interaction with the alleged attacker, i.e., by describing the intrusion process. To our knowledge, very little is done to model this process in quantitative terms. Therefore, based on empirical data collected from intrusion experiments, we have worked out a hypothesis on typical attacker behavior. The hypothesis suggests that the attacking process can be split into three phases: the learning phase, the standard attack phase, and the innovative attack phase. The probability for successful attacks during the learning and innovative phases is expected to be small, although for different reasons. During the standard attack phase it is expected to be considerably higher. The collected data indicates that the breaches during the standard attack phase are statistically equivalent and that the times between breaches are exponentially distributed. This would actually imply that traditional methods for reliability modeling could be applicable     

An empirical framework for user mobility models: Refining and modeling user registration patterns

In this paper, we examine user registration patterns in empirical WLAN traces, identify elusive patterns that are abused as user movements in constructing empirical mobility models, and analyze them to build up a realistic user mobility model. The examination shows that about 38–90% of transitions are irrelevant to actual user movements. In order to refine the elusive movements, we investigate the geographical relationships among APs and propose a filtering framework for removing them from the trace data. We then analyze the impact of the false-positive movements on an empirical mobility model. The numerical results indicate that the proposed framework improves the fidelity of the empirical mobility model. Finally, we devise an analytical model for characterizing realistic user movements, based on the analysis on the elusive user registration patterns, which emulates elusive user registration patterns and generates true user mobile patterns.     

On the relation between socio-economic status and physical mobility

In emerging economies, the socio-economic status is a key element to evaluate social improvement as it provides an understanding of the population's access to housing, education, health or basic services, such as water and electricity. The relationship between such indicators and human physical mobility has been researched mostly in areas like access to medical infrastructures and public transportation. However, such studies have been limited in scope mostly due to the lack of large-scale human mobility information. Nevertheless, the recent adoption of cell phones by large social groups in emerging economies has made it possible to capture large-scale data about human physical mobility, which combined with regional socio-economic levels (SELs), allows to study the relationship between socio-economic indices and human mobility. In this paper, we study the relationship between mobility variables and SELs using cell phone traces. Our results indicate that populations with higher SELs are strongly linked to larger mobility ranges than populations from lower socio-economic status. Finally, we also present a model that formalizes our findings on the relation between SELs and human mobility.     

针对增强型旋转S盒掩码方案的侧信道安全漏洞系统研究

增强型旋转S盒掩码方案（简称RSM2.0）是一种全球知名的抗能量分析防御方案。该方案由DPA Contest国际侧信道大赛组委会首次提出并实现，旨在为高级加密标准AES-128提供高标准的安全防护。通过结合一阶掩码方案与乱序防御这两类经典的侧信道防御技术，组委会宣称RSM2.0具备非模板攻击免疫力并且能够抵抗多种已知的模板类攻击。为了验证RSM2.0方案的实际安全性，本文首先提出了一种通用的漏洞检测方法用以系统性的定位RSM2.0中存在的潜在安全漏洞，并且随后从模板类与非模板类分析两个角度展开研究。模板类研究方面，本文提出了一种泄露指纹利用技术从而能够以近乎100%的概率破解RSM2.0方案的随机掩码防护。为了进一步降低计算以及存储开销，本文又对泄露指纹技术进行优化并首次提出了"最邻近指纹距离均值"评价指标（MOND指标）来客观地衡量不同泄露位置选取条件下泄露指纹攻击方案的性能优劣。在非模板类研究方面，我们设计了4种不同类型的非模板类二阶攻击方案，这些方案利用RSM2.0中乱序防护的设计缺陷，能够有效绕开乱序S盒的能量泄露，从而高效的破解全部128比特的算法主密钥。在实验验证阶段，我们向DPA Contest官方组委会提交了2套模板类攻击代码以及4套非模板类攻击代码。官方评估结果表明，我们提交的模板类最优方案只需使用4条能量曲线以及每条曲线100ms的时间开销即可达到80%的密钥破解全局成功率（GSR），而非模板类最优方案只需257条能量曲线以及每条曲线50ms的处理时间开销即可破解RSM2.0方案。为了进一步提升RSM2.0方案的实际安全性，本文还对RSM2.0的改进对策进行了一系列讨论，以便能够有效应对本文中提出的多种类型的安全威胁。     

Identifying and understanding urban sport areas using Nokia Sports Tracker

Current advancements in pervasive technologies allow users to create and share an increasing amount of whereabouts data. Thus, some rich datasets on human mobility are becoming available on the web. In this paper we extracted approximately 790,000 mobility traces from a web-based repository of GPS tracks—the Nokia Sports Tracker Service. Using data mining mechanisms, we show that this data can be analyzed to uncover daily routines and interesting schemes in the use of public spaces. We first show that our approach supports large-scale analysis of people’s whereabouts by comparing behavioral patterns across cities. Then, using Kernel Density Estimation, we present a mechanism to identify popular sport areas in individual cities. This kind of analysis allows us to highlight human-centered geographies that can support a wide range of applications ranging from location-based services to urban planning.     

Security analysis of CRT-based cryptosystems

A side channel attack (SCA) is a serious attack on the implementation of cryptosystems, which can break the secret key using side channel information such as timing, power consumption, etc. Recently, Boneh et al. showed that SSL is vulnerable to SCA if the attacker gets access to the local network of the server. Therefore, public-key infrastructure eventually becomes a target of SCA. In this paper, we investigate the security of RSA cryptosystem using the Chinese remainder theorem (CRT) in the sense of SCA. Novak first proposed a simple power analysis (SPA) against the CRT part using the difference of message modulo p and modulo q. In this paper, we apply Novak’s attack to the other CRT-based cryptosystems, namely Multi-Prime RSA, Multi-Exponent RSA, Rabin cryptosystem, and HIME(R) cryptosystem. Novak-type attack strictly depends on how to implement the CRT. We examine the operations related to CRT of these cryptosystems, and show that an extended Novak-type attack is effective on them. Moreover, we present a novel attack called zero-multiplication attack. The attacker tries to guess the secret prime by producing ciphertexts that cause a multiplication with zero during the decryption, which is easily detected by power analysis. Our experimental result shows that the timing with the zero multiplication is reduced about 10% from the standard one. Finally, we propose countermeasures against these attacks. The proposed countermeasures are based on the ciphertext blinding, but they require no inversion operation. The overhead of the proposed scheme is only about 1–5% of the whole decryption if the bit length of modulus is 1,024.