Visible to the public Biblio

Filters: Keyword is directed graphs  [Clear All Filters]
2021-09-09
Kanner, Tatiana M., Kanner, Andrey M..  2020.  Testing Software and Hardware Data Security Tools Using the Automata Theory and the Graph Theory. 2020 Ural Symposium on Biomedical Engineering, Radioelectronics and Information Technology (USBEREIT). :615–618.
The article focuses on the application of existing provisions of the automata and graph theories to solving the problem of testing software and hardware data security tools (DST). The software and hardware DST, unlike software ones, include hardware components that implement key security functions, while preventing from using a number of testing methods and tools. In addition to the possibility of applying a particular known testing method or tool to software and hardware DST, what remains acute is the problem of ensuring completeness and optimality of such testing. The developers of various DST do not often have a clear understanding of when they can stop testing and whether the test results allow them to talk about its completeness. Accordingly, testing of DST is often spontaneous, and the developer does not understand whether all the security functions have been tested, whether all the states and all possible sets of parameters have been tested, and whether testing is being carried out in the optimal way. To eliminate these shortcomings, the authors of the article propose to use a mathematical approach based on the theories of automata and graphs to solve the problem of testing software and hardware DST, which can be also used for other software and hardware, as well as software tools and systems. Applying this approach in practice, it is possible to confirm or reject the possibility of ensuring completeness of testing a specific data security tool, as well as identifying specific measures to ensure completeness and optimality of testing.
2021-01-25
Gracy, S., Milošević, J., Sandberg, H..  2020.  Actuator Security Index for Structured Systems. 2020 American Control Conference (ACC). :2993–2998.
Given a network with a set of vulnerable actuators (and sensors), the security index of an actuator equals the minimum number of sensors and actuators that needs to be compromised so as to conduct a perfectly undetectable attack using the said actuator. This paper deals with the problem of computing actuator security indices for discrete-time LTI network systems, using a structured systems framework. We show that the actuator security index is generic, that is for almost all realizations the actuator security index remains the same. We refer to such an index as generic security index (generic index) of an actuator. Given that the security index quantifies the vulnerability of a network, the generic index is quite valuable for large scale energy systems. Our second contribution is to provide graph-theoretic conditions for computing the generic index. The said conditions are in terms of existence of linkings on appropriately-defined directed (sub)graphs. Based on these conditions, we present an algorithm for computing the generic index.
2020-12-11
Slawinski, M., Wortman, A..  2019.  Applications of Graph Integration to Function Comparison and Malware Classification. 2019 4th International Conference on System Reliability and Safety (ICSRS). :16—24.

We classify .NET files as either benign or malicious by examining directed graphs derived from the set of functions comprising the given file. Each graph is viewed probabilistically as a Markov chain where each node represents a code block of the corresponding function, and by computing the PageRank vector (Perron vector with transport), a probability measure can be defined over the nodes of the given graph. Each graph is vectorized by computing Lebesgue antiderivatives of hand-engineered functions defined on the vertex set of the given graph against the PageRank measure. Files are subsequently vectorized by aggregating the set of vectors corresponding to the set of graphs resulting from decompiling the given file. The result is a fast, intuitive, and easy-to-compute glass-box vectorization scheme, which can be leveraged for training a standalone classifier or to augment an existing feature space. We refer to this vectorization technique as PageRank Measure Integration Vectorization (PMIV). We demonstrate the efficacy of PMIV by training a vanilla random forest on 2.5 million samples of decompiled. NET, evenly split between benign and malicious, from our in-house corpus and compare this model to a baseline model which leverages a text-only feature space. The median time needed for decompilation and scoring was 24ms. 11Code available at https://github.com/gtownrocks/grafuple.

2020-12-01
Tanana, D..  2019.  Decentralized Labor Record System Based on Wavelet Consensus Protocol. 2019 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON). :0496—0499.

The labor market involves several untrusted actors with contradicting objectives. We propose a blockchain based system for labor market, which provides benefits to all participants in terms of confidence, transparency, trust and tracking. Our system would handle employment data through new Wavelet blockchain platform. It would change the job market enabling direct agreements between parties without other participants, and providing new mechanisms for negotiating the employment conditions. Furthermore, our system would reduce the need in existing paper workflow as well as in major internet recruiting companies. The key differences of our work from other blockchain based labor record systems are usage of Wavelet blockchain platform, which features metastability, directed acyclic graph system and Turing complete smart contracts platform and introduction of human interaction inside the smart contracts logic, instead of automatic execution of contracts. The results are promising while inconclusive and we would further explore potential of blockchain solutions for labor market problems.

2020-09-28
Yang, Shu, Chen, Ziteng, Cui, Laizhong, Xu, Mingwei, Ming, Zhongxing, Xu, Ke.  2019.  CoDAG: An Efficient and Compacted DAG-Based Blockchain Protocol. 2019 IEEE International Conference on Blockchain (Blockchain). :314–318.
Blockchain is seen as a promising technology to provide reliable and secure services due to its decentralized characteristic. However, because of the limited throughput, current blockchain platforms can not meet the transaction demand in practical use. Though researchers proposed many new solutions, they suffered either decentralization or security issues. In this paper, using Directed Acyclic Graph (DAG) structure, we improve the linear structure of traditional blockchain protocol. In the new structure, blocks are organized in levels and width, which will generate into a compacted DAG structure (CoDAG). To make CoDAG more efficient and secure, we design algorithms and protocols to place the new-generated blocks appropriately. Compared with traditional blockchain protocols, CoDAG improves the security and transaction verification time, and enjoys the consistency and liveness properties of blockchain. Taking adversary parties into consideration, two possible attack strategies are presented in this paper, and we further prove that CoDAG is a secure and robust protocol to resist them. The experimental results show that CoDAG can achieve 394 transactions per second, which is 56 times of Bitcoin's throughput and 26 times of Ethereum's.
2020-01-28
Ayotte, Blaine, Banavar, Mahesh K., Hou, Daqing, Schuckers, Stephanie.  2019.  Fast and Accurate Continuous User Authentication by Fusion of Instance-Based, Free-Text Keystroke Dynamics. 2019 International Conference of the Biometrics Special Interest Group (BIOSIG). :1–6.

Keystroke dynamics study the way in which users input text via their keyboards, which is unique to each individual, and can form a component of a behavioral biometric system to improve existing account security. Keystroke dynamics systems on free-text data use n-graphs that measure the timing between consecutive keystrokes to distinguish between users. Many algorithms require 500, 1,000, or more keystrokes to achieve EERs of below 10%. In this paper, we propose an instance-based graph comparison algorithm to reduce the number of keystrokes required to authenticate users. Commonly used features such as monographs and digraphs are investigated. Feature importance is determined and used to construct a fused classifier. Detection error tradeoff (DET) curves are produced with different numbers of keystrokes. The fused classifier outperforms the state-of-the-art with EERs of 7.9%, 5.7%, 3.4%, and 2.7% for test samples of 50, 100, 200, and 500 keystrokes.

2019-02-14
Zhang, S., Wolthusen, S. D..  2018.  Efficient Control Recovery for Resilient Control Systems. 2018 IEEE 15th International Conference on Networking, Sensing and Control (ICNSC). :1-6.

Resilient control systems should efficiently restore control into physical systems not only after the sabotage of themselves, but also after breaking physical systems. To enhance resilience of control systems, given an originally minimal-input controlled linear-time invariant(LTI) physical system, we address the problem of efficient control recovery into it after removing a known system vertex by finding the minimum number of inputs. According to the minimum input theorem, given a digraph embedded into LTI model and involving a precomputed maximum matching, this problem is modeled into recovering controllability of it after removing a known network vertex. Then, we recover controllability of the residual network by efficiently finding a maximum matching rather than recomputation. As a result, except for precomputing a maximum matching and the following removed vertex, the worst-case execution time of control recovery into the residual LTI physical system is linear.

2019-01-16
Sahay, R., Geethakumari, G., Modugu, K..  2018.  Attack graph — Based vulnerability assessment of rank property in RPL-6LOWPAN in IoT. 2018 IEEE 4th World Forum on Internet of Things (WF-IoT). :308–313.

A significant segment of the Internet of Things (IoT) is the resource constrained Low Power and Lossy Networks (LLNs). The communication protocol used in LLNs is 6LOWPAN (IPv6 over Low-power Wireless Personal Area Network) which makes use of RPL (IPv6 Routing Protocol over Low power and Lossy network) as its routing protocol. In recent times, several security breaches in IoT networks occurred by targeting routers to instigate various DDoS (Distributed Denial of Service) attacks. Hence, routing security has become an important problem in securing the IoT environment. Though RPL meets all the routing requirements of LLNs, it is important to perform a holistic security assessment of RPL as it is susceptible to many security attacks. An important attribute of RPL is its rank property. The rank property defines the placement of sensor nodes in the RPL DODAG (Destination Oriented Directed Acyclic Graphs) based on an Objective Function. Examples of Objective Functions include Expected Transmission Count, Packet Delivery Rate etc. Rank property assists in routing path optimization, reducing control overhead and maintaining a loop free topology through rank based data path validation. In this paper, we investigate the vulnerabilities of the rank property of RPL by constructing an Attack Graph. For the construction of the Attack Graph we analyzed all the possible threats associated with rank property. Through our investigation we found that violation of protocols related to rank property results in several RPL attacks causing topological sub-optimization, topological isolation, resource consumption and traffic disruption. Routing security essentially comprises mechanisms to ensure correct implementation of the routing protocol. In this paper, we also present some observations which can be used to devise mechanisms to prevent the exploitation of the vulnerabilities of the rank property.

2018-02-21
Zheng, H., Zhang, X..  2017.  Optimizing Task Assignment with Minimum Cost on Heterogeneous Embedded Multicore Systems Considering Time Constraint. 2017 ieee 3rd international conference on big data security on cloud (bigdatasecurity), ieee international conference on high performance and smart computing (hpsc), and ieee international conference on intelligent data and security (ids). :225–230.
Time and cost are the most critical performance metrics for computer systems including embedded system, especially for the battery-based embedded systems, such as PC, mainframe computer, and smart phone. Most of the previous work focuses on saving energy in a deterministic way by taking the average or worst scenario into account. However, such deterministic approaches usually are inappropriate in modeling energy consumption because of uncertainties in conditional instructions on processors and time-varying external environments. Through studying the relationship between energy consumption, execution time and completion probability of tasks on heterogeneous multi-core architectures this paper proposes an optimal energy efficiency and system performance model and the OTHAP (Optimizing Task Heterogeneous Assignment with Probability) algorithm to address the Processor and Voltage Assignment with Probability (PVAP) problem of data-dependent aperiodic tasks in real-time embedded systems, ensuring that all the tasks can be done under the time constraint with areal-time embedded systems guaranteed probability. We adopt a task DAG (Directed Acyclic Graph) to model the PVAP problem. We first use a processor scheduling algorithm to map the task DAG onto a set of voltage-variable processors, and then use our dynamic programming algorithm to assign a proper voltage to each task and The experimental results demonstrate our approach outperforms state-of-the-art algorithms in this field (maximum improvement of 24.6%).
2017-12-20
Li, S., Wang, B..  2017.  A Method for Hybrid Bayesian Network Structure Learning from Massive Data Using MapReduce. 2017 ieee 3rd international conference on big data security on cloud (bigdatasecurity), ieee international conference on high performance and smart computing (hpsc), and ieee international conference on intelligent data and security (ids). :272–276.
Bayesian Network is the popular and important data mining model for representing uncertain knowledge. For large scale data it is often too costly to learn the accurate structure. To resolve this problem, much work has been done on migrating the structure learning algorithms to the MapReduce framework. In this paper, we introduce a distributed hybrid structure learning algorithm by combining the advantages of constraint-based and score-and-search-based algorithms. By reusing the intermediate results of MapReduce, the algorithm greatly simplified the computing work and got good results in both efficiency and accuracy.
2017-03-08
Roth, J., Liu, X., Ross, A., Metaxas, D..  2015.  Investigating the Discriminative Power of Keystroke Sound. IEEE Transactions on Information Forensics and Security. 10:333–345.
The goal of this paper is to determine whether keystroke sound can be used to recognize a user. In this regard, we analyze the discriminative power of keystroke sound in the context of a continuous user authentication application. Motivated by the concept of digraphs used in modeling keystroke dynamics, a virtual alphabet is first learned from keystroke sound segments. Next, the digraph latency within the pairs of virtual letters, along with other statistical features, is used to generate match scores. The resultant scores are indicative of the similarities between two sound streams, and are fused to make a final authentication decision. Experiments on both static text-based and free text-based authentications on a database of 50 subjects demonstrate the potential as well as the limitations of keystroke sound.
Çeker, H., Upadhyaya, S..  2015.  Enhanced recognition of keystroke dynamics using Gaussian mixture models. MILCOM 2015 - 2015 IEEE Military Communications Conference. :1305–1310.

Keystroke dynamics is a form of behavioral biometrics that can be used for continuous authentication of computer users. Many classifiers have been proposed for the analysis of acquired user patterns and verification of users at computer terminals. The underlying machine learning methods that use Gaussian density estimator for outlier detection typically assume that the digraph patterns in keystroke data are generated from a single Gaussian distribution. In this paper, we relax this assumption by allowing digraphs to fit more than one distribution via the Gaussian Mixture Model (GMM). We have conducted an experiment with a public data set collected in a controlled environment. Out of 30 users with dynamic text, we obtain 0.08% Equal Error Rate (EER) with 2 components by using GMM, while pure Gaussian yields 1.3% EER for the same data set (an improvement of EER by 93.8%). Our results show that GMM can recognize keystroke dynamics more precisely and authenticate users with higher confidence level.

Darabseh, A., Namin, A. S..  2015.  On Accuracy of Classification-Based Keystroke Dynamics for Continuous User Authentication. 2015 International Conference on Cyberworlds (CW). :321–324.

The aim of this research is to advance the user active authentication using keystroke dynamics. Through this research, we assess the performance and influence of various keystroke features on keystroke dynamics authentication systems. In particular, we investigate the performance of keystroke features on a subset of most frequently used English words. The performance of four features such as i) key duration, ii) flight time latency, iii) diagraph time latency, and iv) word total time duration are analyzed. Two machine learning techniques are employed for assessing keystroke authentications. The selected classification methods are support vector machine (SVM), and k-nearest neighbor classifier (K-NN). The logged experimental data are captured for 28 users. The experimental results show that key duration time offers the best performance result among all four keystroke features, followed by word total time.

Marburg, A., Hayes, M. P..  2015.  SMARTPIG: Simultaneous mosaicking and resectioning through planar image graphs. 2015 IEEE International Conference on Robotics and Automation (ICRA). :5767–5774.

This paper describes Smartpig, an algorithm for the iterative mosaicking of images of a planar surface using a unique parameterization which decomposes inter-image projective warps into camera intrinsics, fronto-parallel projections, and inter-image similarities. The constraints resulting from the inter-image alignments within an image set are stored in an undirected graph structure allowing efficient optimization of image projections on the plane. Camera pose is also directly recoverable from the graph, making Smartpig a feasible solution to the problem of simultaneous location and mapping (SLAM). Smartpig is demonstrated on a set of 144 high resolution aerial images and evaluated with a number of metrics against ground control.

2015-04-30
Kia, S.S., Cortes, J., Martinez, S..  2014.  Periodic and event-triggered communication for distributed continuous-time convex optimization. American Control Conference (ACC), 2014. :5010-5015.

We propose a distributed continuous-time algorithm to solve a network optimization problem where the global cost function is a strictly convex function composed of the sum of the local cost functions of the agents. We establish that our algorithm, when implemented over strongly connected and weight-balanced directed graph topologies, converges exponentially fast when the local cost functions are strongly convex and their gradients are globally Lipschitz. We also characterize the privacy preservation properties of our algorithm and extend the convergence guarantees to the case of time-varying, strongly connected, weight-balanced digraphs. When the network topology is a connected undirected graph, we show that exponential convergence is still preserved if the gradients of the strongly convex local cost functions are locally Lipschitz, while it is asymptotic if the local cost functions are convex. We also study discrete-time communication implementations. Specifically, we provide an upper bound on the stepsize of a synchronous periodic communication scheme that guarantees convergence over connected undirected graph topologies and, building on this result, design a centralized event-triggered implementation that is free of Zeno behavior. Simulations illustrate our results.

Kia, S.S., Cortes, J., Martinez, S..  2014.  Periodic and event-triggered communication for distributed continuous-time convex optimization. American Control Conference (ACC), 2014. :5010-5015.

We propose a distributed continuous-time algorithm to solve a network optimization problem where the global cost function is a strictly convex function composed of the sum of the local cost functions of the agents. We establish that our algorithm, when implemented over strongly connected and weight-balanced directed graph topologies, converges exponentially fast when the local cost functions are strongly convex and their gradients are globally Lipschitz. We also characterize the privacy preservation properties of our algorithm and extend the convergence guarantees to the case of time-varying, strongly connected, weight-balanced digraphs. When the network topology is a connected undirected graph, we show that exponential convergence is still preserved if the gradients of the strongly convex local cost functions are locally Lipschitz, while it is asymptotic if the local cost functions are convex. We also study discrete-time communication implementations. Specifically, we provide an upper bound on the stepsize of a synchronous periodic communication scheme that guarantees convergence over connected undirected graph topologies and, building on this result, design a centralized event-triggered implementation that is free of Zeno behavior. Simulations illustrate our results.