On the hardness of approximating the Min-Hack problem

Ramkumar Chinchani; Duc Ha; Anusha Iyer; Hung Q. Ngo; Shambhu Upadhyaya

doi:10.1007/s10878-005-1413-8

On the hardness of approximating the Min-Hack problem

Ramkumar Chinchani
, Duc Ha
, Anusha Iyer
, Hung Q. Ngo
, Shambhu Upadhyaya

Department of Computer Science and Engineering

SUNY Buffalo

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

We show several hardness results for the Minimum Hacking problem, which roughly can be described as the problem of finding the best way to compromise a target node given a few initial compromised nodes in a network. We give several reductions to show that Minimum Hacking is not approximable to within 2 ^{(log n)1 δ} where δ = 1-.1/loglog^c n, for any c < 1/2. We also analyze some heuristics on this problem.

Original language	English
Pages (from-to)	295-311
Number of pages	17
Journal	Journal of Combinatorial Optimization
Volume	9
Issue number	3
DOIs	https://doi.org/10.1007/s10878-005-1413-8
State	Published - May 2005

Keywords

Computer security
Hardness of threat analysis

Access to Document

10.1007/s10878-005-1413-8

Cite this

@article{93d0e51dccdd494d8fd340492b000a3c,

title = "On the hardness of approximating the Min-Hack problem",

abstract = "We show several hardness results for the Minimum Hacking problem, which roughly can be described as the problem of finding the best way to compromise a target node given a few initial compromised nodes in a network. We give several reductions to show that Minimum Hacking is not approximable to within 2 (log n)1 δ where δ = 1-.1/loglogc n, for any c < 1/2. We also analyze some heuristics on this problem.",

keywords = "Computer security, Hardness of threat analysis",

author = "Ramkumar Chinchani and Duc Ha and Anusha Iyer and Ngo, \{Hung Q.\} and Shambhu Upadhyaya",

year = "2005",

month = may,

doi = "10.1007/s10878-005-1413-8",

language = "English",

volume = "9",

pages = "295--311",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - On the hardness of approximating the Min-Hack problem

AU - Chinchani, Ramkumar

AU - Ha, Duc

AU - Iyer, Anusha

AU - Ngo, Hung Q.

AU - Upadhyaya, Shambhu

PY - 2005/5

Y1 - 2005/5

N2 - We show several hardness results for the Minimum Hacking problem, which roughly can be described as the problem of finding the best way to compromise a target node given a few initial compromised nodes in a network. We give several reductions to show that Minimum Hacking is not approximable to within 2 (log n)1 δ where δ = 1-.1/loglogc n, for any c < 1/2. We also analyze some heuristics on this problem.

AB - We show several hardness results for the Minimum Hacking problem, which roughly can be described as the problem of finding the best way to compromise a target node given a few initial compromised nodes in a network. We give several reductions to show that Minimum Hacking is not approximable to within 2 (log n)1 δ where δ = 1-.1/loglogc n, for any c < 1/2. We also analyze some heuristics on this problem.

KW - Computer security

KW - Hardness of threat analysis

UR - https://www.scopus.com/pages/publications/22044441703

U2 - 10.1007/s10878-005-1413-8

DO - 10.1007/s10878-005-1413-8

M3 - Article

AN - SCOPUS:22044441703

SN - 1382-6905

VL - 9

SP - 295

EP - 311

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 3

ER -

On the hardness of approximating the Min-Hack problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this