Security-aware optimization for ubiquitous computing systems with SEAT graph approach

Meikang Qiu, Lei Zhang, Zhong Ming, Zhi Chen, Xiao Qin, Laurence T. Yang

Research output: Contribution to journalArticlepeer-review

98 Scopus citations


For ubiquitous computing systems, security has become a new metric that designers should consider throughout the design process, along with other metrics such as performance and energy consumption. A combination of selected cryptographic algorithms for required security services forms a security strategy for the application. In this paper, we propose methods to generate security strategies to achieve the maximal overall security strength while meeting the real-time constraint. In order to express security requirements of an application, we propose a novel graph model called Security-Aware Task (SEAT) graph model to represent real-time constraints and precedence relationships among tasks. Based on the SEAT graph approach, we propose an optimal algorithm, Integer Linear Programming Security Optimization (ILP-SOP). For the special structures such as simple path graph and tree, we propose two dynamic programming based algorithms (DPSOP-path/tree) to generate the optimal security strategy. Experiment results demonstrate the correctness and efficiency of our proposed method. The experimental results show that, by using our proposed techniques, the security strength can be improved by 44.3% on average.

Original languageEnglish
Pages (from-to)518-529
Number of pages12
JournalJournal of Computer and System Sciences
Issue number5
StatePublished - Aug 2013

Bibliographical note

Funding Information:
This work was supported in part by the NSF CNS-1249223, NSFC 61071061, the Univ. of Kentucky Start Up Fund; NSFC 61170077, SZ-HK Innovation Circle project ZYB200907060012A, NSF GD:10351806001000000, S & T project of SZ JC200903120046A; the NSF CNS-0969013, CNS-0917021, and CNS-1018108; the NSF CNS-0915762 (CSR), CCF-08452578 (CAREER), CNS-0917137 (CSR).


  • Cryptographic algorithm
  • Real-time
  • Schedule
  • Security
  • Ubiquitous system

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science
  • Applied Mathematics
  • Computer Networks and Communications
  • Computational Theory and Mathematics


Dive into the research topics of 'Security-aware optimization for ubiquitous computing systems with SEAT graph approach'. Together they form a unique fingerprint.

Cite this