Sage Journals: Discover world-class research

Abstract

Managed security services (MSS) are becoming increasingly popular today. In MSS, enterprises contract a security firm such as Symantec or IBM to manage security of their enterprise network. MSS vendors thus have a small pool of cybersecurity analysts who must monitor many different alerts. In this paper, we study the problem of allocating cybersecurity analysts to alerts generated by intrusion detection systems and other security software. In particular, given an enterprise network (or set of enterprise networks) and information about the value of assets stored at a node (e.g. computer, router) in the network, together with probabilities of compromising a neighbor of a compromised vertex, we show that annotated probabilistic temporal (APT) logic programs allow a defender to express knowledge about the network that captures the probabilities that different nodes will be attacked. In addition, certain APT logic computations, in conjunction with a Stackelberg game theoretic formalization, enable us to capture the attacker’s maximal probability of success as well as his ability to maximize damage. We show how the defender can come up with optimal allocations of tasks to cybersecurity analysts, taking both network information into account as well as a behavioral model of the attacker into account. We show correctness and complexity theorems for both the attacker and the defender. We develop a prototype implementation of three algorithms for the defender that optimize the defender’s objectives and show that these algorithms work well on realistic network sizes.

Keywords

Enterprise systems logic programs computer security behavior modeling

Get full access to this article

View all access options for this article.

References

K.J.

Ahn and

Guha, Linear programming in the semi-streaming model with application to the maximum matching problem, Information and Computation 222 (2013), 59–79. doi:10.1016/j.ic.2012.10.006.

K.G.

Anagnostakis,

Sidiroglou,

Akritidis,

Xinidis,

Markatos and

A.D.

Keromytis, Detecting targeted attacks using shadow honeypots, in: Proceedings of the 14th Conference on USENIX Security Symposium – Volume 14 (SSYM’05), USENIX Association, Berkeley, CA, USA, 2005, pp. 9–9.

J.P.

Anderson, Computer security threat monitoring and surveillance, Technical report, James P. Anderson Co., Fort Washington, PA, 1980.

C.A.

Ardagna,

Cremonini,

Damiani,

De Capitani di Vimercati and

Samarati, Supporting location-based conditions in access control policies, in: Proceedings of the 2006 ACM Symposium on Information, Computer and Communications Security, ACM, 2006, pp. 212–222.

Azaria,

Richardson,

Kraus and

V.S.

Subrahmanian, Behavioral analysis of insider threat: A survey and bootstrapped prediction in imbalanced data, IEEE Transactions on Computational Social Systems 1(2) (2014), 135–155. doi:10.1109/TCSS.2014.2377811.

Barbara and

Jajodia (eds), Application of Data Mining in Computer Security, Vol. 6, Springer, 2002.

Başar, A tutorial on dynamic and differential games, in: Dynamic Games and Applications in Economics, Springer, 1986, pp. 1–25.

Basin,

Caleiro,

Ramos and

Viganò, Distributed temporal logic for the analysis of security protocol models, Theoretical Computer Science 412(31) (2011), 4007–4043. doi:10.1016/j.tcs.2011.04.006.

Bell,

Nerode,

R.T.

Ng and

V.S.

Subrahmanian, Implementing deductive databases by linear programming, in: Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, ACM, 1992, pp. 283–292. doi:10.1145/137097.137892.

10.

Bell,

Nerode,

R.T.

Ng and

V.S.

Subrahmanian, Mixed integer programming methods for computing nonmonotonic deductive databases, Journal of the ACM (JACM) 41(6) (1994), 1178–1215. doi:10.1145/195613.195637.

11.

Bieber and

Cuppens, Expression of confidentiality policies with deontic logic, 1992.

12.

Bishop, What is computer security?, Security & Privacy, IEEE 1(1) (2003), 67–69. doi:10.1109/MSECP.2003.1176998.

13.

Biskup and

P.A.

Bonatti, Lying versus refusal for known potential secrets, Data & Knowledge Engineering 38(2) (2001), 199–222. doi:10.1016/S0169-023X(01)00024-6.

14.

Bonatti,

Kraus and

V.S.

Subrahmanian, Declarative foundations of secure deductive databases, in: Database Theory – ICDT’92, Springer, 1992, pp. 391–406. doi:10.1007/3-540-56039-4_55.

15.

P.A.

Bonatti,

Kraus and

V.S.

Subrahmanian, Foundations of secure deductive databases, IEEE Transactions on Knowledge and Data Engineering 7(3) (1995), 406–422. doi:10.1109/69.390247.

16.

P.A.

Bonatti and

Samarati, Logics for authorizations and security, in: Logics for Emerging Applications of Databases, Springer, 2004, pp. 277–323. doi:10.1007/978-3-642-18690-5_8.

17.

P.P.

Bonissone, Summarizing and propagating uncertain information with triangular norms, International Journal of Approximate Reasoning 1(1) (1987), 71–101. doi:10.1016/0888-613X(87)90005-3.

18.

P.P.

Bonissone, Using T-norm-based uncertainty calculi in a naval situation assessment application, Int. J. Approx. Reasoning 2(3) (1988), 328–329.

19.

Bonneau,

Herley,

P.C.

Van Oorschot and

Stajano, The quest to replace passwords: A framework for comparative evaluation of web authentication schemes, in: Security and Privacy (SP), 2012 IEEE Symposium on, IEEE, 2012, pp. 553–567. doi:10.1109/SP.2012.44.

20.

Boole, An Investigation of the Laws of Thought: On Which Are Founded the Mathematical Theories of Logic and Probabilities, Dover Publications, 1854.

21.

Common Weakness Scoring System, 2011, https://cwe.mitre.org/.

22.

Corin and

Etalle, An Improved Constraint-Based System for the Verification of Security Protocols, Springer, 2002.

23.

D’Amico and

Whitley, The real work of computer network defense analysts: The analysis roles and processes that transform network data into security situation awareness, in: Proceedings of the Workshop on Visualization for Computer Security, 2008, pp. 19–37.

24.

Datta,

Derek,

J.C.

Mitchell and

Pavlovic, A derivation system and compositional logic for security protocols, Journal of Computer Security 13(3) (2005), 423–482. doi:10.3233/JCS-2005-13304.

25.

Dekhtyar,

M.I.

Dekhtyar and

V.S.

Subrahmanian, Temporal probabilistic logic programs, in: ICLP,

De Schreye, ed., MIT Press, 1999, pp. 109–123.

26.

D.E.

Denning, An intrusion-detection model, in: Proceedings of IEEE Symposium on Security and Privacy, Oakland, CA, 1986, pp. 118–131.

27.

D.E.

Denning, An intrusion-detection model, IEEE Trans. Software Eng. 13(2) (1987), 222–232. doi:10.1109/TSE.1987.232894.

28.

Desrosiers and

M.E.

Lübbecke, A Primer in Column Generation, Springer, 2005.

29.

DeTreville, Binder, a logic-based security language, in: Proceedings. 2002 IEEE Symposium on Security and Privacy, IEEE, 2002, pp. 105–113. doi:10.1109/SECPRI.2002.1004365.

30.

J.P.

Dickerson,

G.I.

Simari,

V.S.

Subrahmanian and

Kraus, A graph-theoretic approach to protect static and moving targets from adversaries, in: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: Volume 1-Volume 1, International Foundation for Autonomous Agents and Multiagent Systems, 2010, pp. 299–306.

31.

R.F.

Erbacher and

S.E.

Hutchinson, Extending case-based reasoning to network alert reporting, in: 2012 ASE International Conference on Cyber Security, 2012, pp. 187–194. doi:10.1109/CyberSecurity.2012.31.

32.

Eronen and

Zitting, An expert system for analyzing firewall rules, in: Proceedings of the 6th Nordic Workshop on Secure IT Systems (NordSec 2001), 2001, pp. 100–107.

33.

Glasgow,

MacEwen and

Panangaden, A logic for reasoning about security, ACM Transactions on Computer Systems (TOCS) 10(3) (1992), 226–264. doi:10.1145/146937.146940.

34.

R.L.

Graham,

E.L.

Lawler,

J.K.

Lenstra and

A.H.G.

Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics 5 (1979), 287–326. doi:10.1016/S0167-5060(08)70356-X.

35.

J.Y.

Halpern and

Weissman, Using first-order logic to reason about policies, ACM Transactions on Information and System Security (TISSEC) 11(4) (2008), 21.

36.

M.J.

Hasan, Belief reasoning in MLS deductive databases, ACM SIGMOD Record 28(2) (1999), 109–120.

37.

Hooker, Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction, Vol. 2, John Wiley & Sons, 2011.

38.

Jaffar and

J.-L.

Lassez, Constraint logic programming, in: Proceedings of the 14th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL ’87), ACM, New York, NY, USA, 1987, pp. 111–119. doi:10.1145/41625.41635.

39.

Jajodia,

Noel,

Kalapa,

Albanese and

Williams, Cauldron: Mission-centric cyber situational awareness with defense in depth, in: Proceedings of the Military Communications Conference (MILCOM 2011), 2011.

40.

Jajodia,

Samarati,

M.L.

Sapino and

V.S.

Subrahmanian, Flexible support for multiple access control policies, ACM Transactions on Database Systems (TODS) 26(2) (2001), 214–260. doi:10.1145/383891.383894.

41.

R.G.

Jeroslow, Computation-oriented reductions of predicate to propositional logic, Decision Support Systems 4(2) (1988), 183–197. doi:10.1016/0167-9236(88)90128-5.

42.

Kern-Isberner and

Lukasiewicz, Combining probabilistic logic programming with the power of maximum entropy, Artificial Intelligence 157(1) (2004), 139–202. doi:10.1016/j.artint.2004.04.003.

43.

Kim and

M.H.

Kang, Determining asset criticality for cyber defense, Naval Research Laboratory (2011).

44.

Korzhyk,

Yin,

Kiekintveld,

Conitzer and

Tambe, Stackelberg vs. Nash in security games: An extended investigation of interchangeability, equivalence, and uniqueness, J. Artif. Intell. Res. (JAIR) 41 (2011), 297–327.

45.

Li and

J.C.

Mitchell, Datalog with constraints: A foundation for trust management languages, in: Practical Aspects of Declarative Languages, Springer, 2003, pp. 58–73. doi:10.1007/3-540-36388-2_6.

46.

J.W.

Lloyd, Foundations of Logic Programming, 2nd edn, Springer, 1987.

47.

Mell,

Scarfone and

Romanosky, Common vulnerability scoring system, Security Privacy, IEEE 4(6) (2006), 85–89.

48.

G.L.

Nemhauser,

L.A.

Wolsey and

M.L.

Fisher, An analysis of approximations for maximizing submodular set functions – I, Mathematical Programming 14(1) (1978), 265–294. doi:10.1007/BF01588971.

49.

Ng and

V.S.

Subrahmanian, Probabilistic logic programming, Information and Computation 101(2) (1992), 150–201. doi:10.1016/0890-5401(92)90061-J.

50.

N.J.

Nilsson, Probabilistic logic, Artificial Intelligence 28(1) (1986), 71–87. doi:10.1016/0004-3702(86)90031-7.

51.

Paruchuri, Playing games for security: An efficient exact algorithm for solving Bayesian Stackelberg games, in: AAMAS, 2008.

52.

Paxson, Bro: A system for detecting network intruders in real-time, Computer Networks 31(23–24) (1999), 2435–2463. doi:10.1016/S1389-1286(99)00112-7.

53.

Rahmani,

Sahli and

Kamoun, DDoS flooding attack detection scheme based on F-divergence, Computer Communications 35(11) (2012), 1380–1391. doi:10.1016/j.comcom.2012.04.002.

54.

Raman and

I.E.

Grossmann, Modelling and computational techniques for logic based integer programming, Computers & Chemical Engineering 18(7) (1994), 563–578. doi:10.1016/0098-1354(93)E0010-7.

55.

Samarati and

De Capitani di Vimercati, Access control: Policies, models, and mechanisms, in: Foundations of Security Analysis and Design, Springer, 2001, pp. 137–196. doi:10.1007/3-540-45608-2_3.

56.

Serra,

Jajodia,

Pugliese,

Rullo and

V.S.

Subrahmanian, Pareto-optimal adversarial defense of enterprise systems, ACM Transactions on Information and System Security (TISSEC) 17(3) (2015), 11.

57.

Shakarian,

Parker,

G.I.

Simari and

V.S.

Subrahmanian, Annotated probabilistic temporal logic, ACM Trans. Comput. Log. 12(2) (2011), 14.

58.

Shakarian,

G.I.

Simari and

V.S.

Subrahmanian, Annotated probabilistic temporal logic: Approximate fixpoint implementation, ACM Trans. Comput. Log. 13(2) (2012), 13.

59.

Sommer and

Paxson, Outside the closed world: On using machine learning for network intrusion detection, in: Proceedings of IEEE Symposium on Security and Privacy, 2010, pp. 305–316.

60.

Stouppa and

Studer, Data privacy for ALC knowledge bases, in: Logical Foundations of Computer Science, Springer, 2009, pp. 409–421. doi:10.1007/978-3-540-92687-0_28.

61.

USMA, 2009, http://www.usma.edu/crc/SitePages/DataSets.aspx.

62.

Winslett,

Smith and

Qian, Formal query languages for secure relational databases, ACM Transactions on Database Systems (TODS) 19(4) (1994), 626–662. doi:10.1145/195664.195675.

63.

Yu,

Zhou,

Jia,

Guo,

Xiang and

Tang, Discriminating DDoS attacks from flash crowds using flow correlation coefficient, IEEE Transactions on Parallel and Distributed Systems 23(6) (2012), 1073–1080.

64.

Zimmerman, The Strategies of a World-Class Cybersecurity Operations Center, The MITRE Corporation, 2014.

Using temporal probabilistic logic for optimal monitoring of security events with limited resources

Abstract

Keywords

Get full access to this article

References