Visible to the public Biblio

Filters: Keyword is dynamic programming  [Clear All Filters]
2021-06-02
Gohari, Parham, Hale, Matthew, Topcu, Ufuk.  2020.  Privacy-Preserving Policy Synthesis in Markov Decision Processes. 2020 59th IEEE Conference on Decision and Control (CDC). :6266—6271.
In decision-making problems, the actions of an agent may reveal sensitive information that drives its decisions. For instance, a corporation's investment decisions may reveal its sensitive knowledge about market dynamics. To prevent this type of information leakage, we introduce a policy synthesis algorithm that protects the privacy of the transition probabilities in a Markov decision process. We use differential privacy as the mathematical definition of privacy. The algorithm first perturbs the transition probabilities using a mechanism that provides differential privacy. Then, based on the privatized transition probabilities, we synthesize a policy using dynamic programming. Our main contribution is to bound the "cost of privacy," i.e., the difference between the expected total rewards with privacy and the expected total rewards without privacy. We also show that computing the cost of privacy has time complexity that is polynomial in the parameters of the problem. Moreover, we establish that the cost of privacy increases with the strength of differential privacy protections, and we quantify this increase. Finally, numerical experiments on two example environments validate the established relationship between the cost of privacy and the strength of data privacy protections.
2021-05-18
Li, Zesong, Yang, Hui, Ge, Junwei, Yu, Qinyong.  2020.  Research on Dynamic Detection Method of Buffer Overflow Vulnerabilities Based on Complete Boundary Test. 2020 IEEE 6th International Conference on Computer and Communications (ICCC). :2246–2250.
At present, when the device management application programs the devices (such as mobile terminals, Internet of things terminals and devices, etc.), buffer overflow will inevitably occur due to the defects of filter input condition setting, variable type conversion error, logical judgment error, pointer reference error and so on. For this kind of software and its running environment, it is difficult to reduce the false positive rate and false negative rate with traditional static detection method for buffer overflow vulnerability, while the coverage rate of dynamic detection method is still insufficient and it is difficult to achieve full automation. In view of this, this paper proposes an automatic dynamic detection method based on boundary testing, which has complete test data set and full coverage of defects. With this method, the input test points of the software system under test are automatically traversed, and each input test point is analyzed automatically to generate complete test data; driven by the above complete test data, the software under test runs automatically, in which the embedded dynamic detection code automatically judges the conditions of overflow occurrence, and returns the overflow information including the location of the error code before the overflow really occurs. Because the overflow can be located accurately without real overflow occurrence, this method can ensure the normal detection of the next input test point, thus ensuring the continuity of the whole automatic detection process and the full coverage of buffer overflow detection. The test results show that all the indexes meet the requirements of the method and design.
2020-12-11
Phu, T. N., Hoang, L., Toan, N. N., Tho, N. Dai, Binh, N. N..  2019.  C500-CFG: A Novel Algorithm to Extract Control Flow-based Features for IoT Malware Detection. 2019 19th International Symposium on Communications and Information Technologies (ISCIT). :568—573.

{Static characteristic extraction method Control flow-based features proposed by Ding has the ability to detect malicious code with higher accuracy than traditional Text-based methods. However, this method resolved NP-hard problem in a graph, therefore it is not feasible with the large-size and high-complexity programs. So, we propose the C500-CFG algorithm in Control flow-based features based on the idea of dynamic programming, solving Ding's NP-hard problem in O(N2) time complexity, where N is the number of basic blocks in decom-piled executable codes. Our algorithm is more efficient and more outstanding in detecting malware than Ding's algorithm: fast processing time, allowing processing large files, using less memory and extracting more feature information. Applying our algorithms with IoT data sets gives outstanding results on 2 measures: Accuracy = 99.34%

2020-07-10
Cai, Zhipeng, Miao, Dongjing, Li, Yingshu.  2019.  Deletion Propagation for Multiple Key Preserving Conjunctive Queries: Approximations and Complexity. 2019 IEEE 35th International Conference on Data Engineering (ICDE). :506—517.

This paper studies the deletion propagation problem in terms of minimizing view side-effect. It is a problem funda-mental to data lineage and quality management which could be a key step in analyzing view propagation and repairing data. The investigated problem is a variant of the standard deletion propagation problem, where given a source database D, a set of key preserving conjunctive queries Q, and the set of views V obtained by the queries in Q, we try to identify a set T of tuples from D whose elimination prevents all the tuples in a given set of deletions on views △V while preserving any other results. The complexity of this problem has been well studied for the case with only a single query. Dichotomies, even trichotomies, for different settings are developed. However, no results on multiple queries are given which is a more realistic case. We study the complexity and approximations of optimizing the side-effect on the views, i.e., find T to minimize the additional damage on V after removing all the tuples of △V. We focus on the class of key-preserving conjunctive queries which is a dichotomy for the single query case. It is surprising to find that except the single query case, this problem is NP-hard to approximate within any constant even for a non-trivial set of multiple project-free conjunctive queries in terms of view side-effect. The proposed algorithm shows that it can be approximated within a bound depending on the number of tuples of both V and △V. We identify a class of polynomial tractable inputs, and provide a dynamic programming algorithm to solve the problem. Besides data lineage, study on this problem could also provide important foundations for the computational issues in data repairing. Furthermore, we introduce some related applications of this problem, especially for query feedback based data cleaning.

2019-06-24
You, Y., Li, Z., Oechtering, T. J..  2018.  Optimal Privacy-Enhancing And Cost-Efficient Energy Management Strategies For Smart Grid Consumers. 2018 IEEE Statistical Signal Processing Workshop (SSP). :826–830.

The design of optimal energy management strategies that trade-off consumers' privacy and expected energy cost by using an energy storage is studied. The Kullback-Leibler divergence rate is used to assess the privacy risk of the unauthorized testing on consumers' behavior. We further show how this design problem can be formulated as a belief state Markov decision process problem so that standard tools of the Markov decision process framework can be utilized, and the optimal solution can be obtained by using Bellman dynamic programming. Finally, we illustrate the privacy-enhancement and cost-saving by numerical examples.

2019-05-01
Borra, V. S., Debnath, K..  2018.  Dynamic programming for solving unit commitment and security problems in microgrid systems. 2018 IEEE International Conference on Innovative Research and Development (ICIRD). :1–6.

In order to meet the demand of electrical energy by consumers, utilities have to maintain the security of the system. This paper presents a design of the Microgrid Central Energy Management System (MCEMS). It will plan operation of the system one-day advance. The MCEMS will adjust itself during operation if a fault occurs anywhere in the generation system. The proposed approach uses Dynamic Programming (DP) algorithm solves the Unit Commitment (UC) problem and at the same time enhances the security of power system. A case study is performed with ten subsystems. The DP is used to manage the operation of the subsystems and determines the UC on the situation demands. Faults are applied to the system and the DP corrects the UC problem with appropriate power sources to maintain reliability supply. The MATLAB software has been used to simulate the operation of the system.

2019-02-08
Xie, H., Lv, K., Hu, C..  2018.  An Improved Monte Carlo Graph Search Algorithm for Optimal Attack Path Analysis. 2018 17th IEEE International Conference On Trust, Security And Privacy In Computing And Communications/ 12th IEEE International Conference On Big Data Science And Engineering (TrustCom/BigDataSE). :307-315.

The problem of optimal attack path analysis is one of the hotspots in network security. Many methods are available to calculate an optimal attack path, such as Q-learning algorithm, heuristic algorithms, etc. But most of them have shortcomings. Some methods can lead to the problem of path loss, and some methods render the result un-comprehensive. This article proposes an improved Monte Carlo Graph Search algorithm (IMCGS) to calculate optimal attack paths in target network. IMCGS can avoid the problem of path loss and get comprehensive results quickly. IMCGS is divided into two steps: selection and backpropagation, which is used to calculate optimal attack paths. A weight vector containing priority, host connection number, CVSS value is proposed for every host in an attack path. This vector is used to calculate the evaluation value, the total CVSS value and the average CVSS value of a path in the target network. Result for a sample test network is presented to demonstrate the capabilities of the proposed algorithm to generate optimal attack paths in one single run. The results obtained by IMCGS show good performance and are compared with Ant Colony Optimization Algorithm (ACO) and k-zero attack graph.

2019-01-31
Chen, Y., Wu, B..  2018.  An Efficient Algorithm for Minimal Edit Cost of Graph Degree Anonymity. 2018 IEEE International Conference on Applied System Invention (ICASI). :574–577.

Personal privacy is an important issue when publishing social network data. An attacker may have information to reidentify private data. So, many researchers developed anonymization techniques, such as k-anonymity, k-isomorphism, l-diversity, etc. In this paper, we focus on graph k-degree anonymity by editing edges. Our method is divided into two steps. First, we propose an efficient algorithm to find a new degree sequence with theoretically minimal edit cost. Second, we insert and delete edges based on the new degree sequence to achieve k-degree anonymity.

2019-01-21
Wang, X., Hou, Y., Huang, X., Li, D., Tao, X., Xu, J..  2018.  Security Analysis of Key Extraction from Physical Measurements with Multiple Adversaries. 2018 IEEE International Conference on Communications Workshops (ICC Workshops). :1–6.
In this paper, security of secret key extraction scheme is evaluated for private communication between legitimate wireless devices. Multiple adversaries that distribute around these legitimate wireless devices eavesdrop on the data transmitted between them, and deduce the secret key. Conditional min-entropy given the view of those adversaries is utilized as security evaluation metric in this paper. Besides, the wiretap channel model and hidden Markov model (HMM) are regarded as the channel model and a dynamic programming approach is used to approximate conditional min- entropy. Two algorithms are proposed to mathematically calculate the conditional min- entropy by combining the Viterbi algorithm with the Forward algorithm. Optimal method with multiple adversaries (OME) algorithm is proposed firstly, which has superior performance but exponential computation complexity. To reduce this complexity, suboptimal method with multiple adversaries (SOME) algorithm is proposed, using performance degradation for the computation complexity reduction. In addition to the theoretical analysis, simulation results further show that the OME algorithm indeed has superior performance as well as the SOME algorithm has more efficient computation.
2018-09-28
Yang, Y., Wunsch, D., Yin, Y..  2017.  Hamiltonian-driven adaptive dynamic programming for nonlinear discrete-time dynamic systems. 2017 International Joint Conference on Neural Networks (IJCNN). :1339–1346.

In this paper, based on the Hamiltonian, an alternative interpretation about the iterative adaptive dynamic programming (ADP) approach from the perspective of optimization is developed for discrete time nonlinear dynamic systems. The role of the Hamiltonian in iterative ADP is explained. The resulting Hamiltonian driven ADP is able to evaluate the performance with respect to arbitrary admissible policies, compare two different admissible policies and further improve the given admissible policy. The convergence of the Hamiltonian ADP to the optimal policy is proven. Implementation of the Hamiltonian-driven ADP by neural networks is discussed based on the assumption that each iterative policy and value function can be updated exactly. Finally, a simulation is conducted to verify the effectiveness of the presented Hamiltonian-driven ADP.

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-03-08
Li, X..  2015.  A Quantity-Flexibility Contract in Two-Stage Decision with Supply Chain Coordination. 2015 11th International Conference on Computational Intelligence and Security (CIS). :109–112.

We study a quantity-flexibility supply contract between a manufacturer and a retailer in two periods. The retailer can get a low wholesale price within a fixed quantity and adjust the quantity at the end of the first period. The retailer can adjust the order quantities after the first period based on updated inventory status by paying a higher per-unit price for the incremental units or obtaining a buyback price per-unit for the returning units. By developing a two-period dynamic programming model in this paper, we first obtain an optimal replenishment strategy for the retailer when the manufacturer's price scheme is known. Then we derive an proper pricing scheme for the manufacturer by assuming that the supply chain is coordinated. The numerical results show some managerial insights by comparing this coordination scheme with Stackelberg game.

2015-05-05
Juzi Zhao, Subramaniam, S., Brandt-Pearce, M..  2014.  Intradomain and interdomain QoT-aware RWA for translucent optical networks. Optical Communications and Networking, IEEE/OSA Journal of. 6:536-548.

Physical impairments in long-haul optical networks mandate that optical signals be regenerated within the (so-called translucent) network. Being expensive devices, regenerators are expected to be allocated sparsely and must be judiciously utilized. Next-generation optical-transport networks will include multiple domains with diverse technologies, protocols, granularities, and carriers. Because of confidentiality and scalability concerns, the scope of network-state information (e.g., topology, wavelength availability) may be limited to within a domain. In such networks, the problem of routing and wavelength assignment (RWA) aims to find an adequate route and wavelength(s) for lightpaths carrying end-to-end service demands. Some state information may have to be explicitly exchanged among the domains to facilitate the RWA process. The challenge is to determine which information is the most critical and make a wise choice for the path and wavelength(s) using the limited information. Recently, a framework for multidomain path computation called backward-recursive path-computation (BRPC) was standardized by the Internet Engineering Task Force. In this paper, we consider the RWA problem for connections within a single domain and interdomain connections so that the quality of transmission (QoT) requirement of each connection is satisfied, and the network-level performance metric of blocking probability is minimized. Cross-layer heuristics that are based on dynamic programming to effectively allocate the sparse regenerators are developed, and extensive simulation results are presented to demonstrate their effectiveness.