IP Library › Granted Patent US 12,225,035
Granted Patent B2
US 12,225,035 · App. 18/378,002 · Granted Feb 11, 2025

Systems, methods, and media for defending computing systems from attack

Inventors: Yuan Jochen Kang (New York, NY); Salvatore Stolfo (New York, NY)
Assignee: The Trustees of Columbia University in the City of New York
H04L63/1425G06F7/582G06F9/542G06F21/54G06F21/602H04L63/1416
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,225,035
App. No.
18/378,002
Granted
Feb 11, 2025
Kind
B2
Abstract

Mechanisms for defending a computing system from attack are provided. The mechanisms include: maintaining a round counter that tracks a round number for a local host; determining a location in a graph for each of a plurality of hosts including the local host; determining monitor hosts of the plurality of hosts that are monitoring the local host; determining monitoree hosts of the plurality of hosts that are being monitored by the local host; sending a message to each of the monitor hosts identifying a value of the round counter; forwarding a first set of heartbeat messages from previous monitoree hosts to the monitor hosts; attempting to receive messages from the monitoree hosts; determining whether any messages were not received from the monitoree hosts; and in response to determining that one or more messages were not received from the monitoree hosts, generating an alert.

Claims (52)

1. A system for defending a computing system from attack, comprising:

a memory; and

a hardware processor coupled to the memory and configured to execute a local host that is configured to:

maintain a round counter that tracks a round number;

determine whether the round counter is divisible by a diameter of a graph identifying each of a plurality of hosts including the local host;

in response to determining that the round counter is divisible by the diameter of the graph, determine a location in the graph for each of the plurality of hosts including the local host;

determine a monitor host of the plurality of hosts that is monitoring the local host;

determine a monitoree host of the plurality of hosts that is monitored by the local host;

send a message to the monitor host identifying a value of the round counter;

forward a first set of heartbeat messages previously sent from the monitoree host to the monitor host;

attempt to receive a message from the monitoree host;

determine whether a message was not received from the monitoree host; and

in response to determining that a message was not received from the monitoree host, generate an alert.

2. The system of claim 1 , wherein the directed graph is a DeBruijn graph.

3. The system of claim 1 , wherein the location in the graph for each of a plurality of hosts is determined using a pseudo-random function.

4. The system of claim 3 , wherein the location in the graph for each of a plurality of hosts is determined using the pseudo-random function based on a shared key, the round counter, and an identifier for each of the plurality of hosts.

5. The system of claim 1 , wherein the message sent to the monitor host identifying a value of the round counter is signed.

6. The system of claim 1 , wherein the hardware processor is configured to generate an alert in response to determining whether any received messages are invalid.

7. The system of claim 1 , wherein the hardware processor is configured to determine whether any heartbeat messages were received early.

8. A method for defending a computing system from attack, comprising:

maintaining a round counter that tracks a round number for a local host using a hardware processor;

determining whether the round counter is divisible by a diameter of a graph identifying each of a plurality of hosts including the local host;

in response to determining that the round counter is divisible by the diameter of the graph, determining a location in the graph for each of the plurality of hosts including the local host using the hardware processor;

determining a monitor host of the plurality of hosts that is monitoring the local host using the hardware processor;

determining a monitoree host of the plurality of hosts that is monitored by the local host using the hardware processor;

sending a message to the monitor host identifying a value of the round counter using the hardware processor;

forwarding a first set of heartbeat messages from the monitoree host to the monitor host using the hardware processor;

attempting to receive a message from the monitoree host using the hardware processor;

determining whether a message was not received from the monitoree host using the hardware processor; and

in response to determining that a message was not received from the monitoree host, generating an alert using the hardware processor.

9. The method of claim 8 , wherein the directed graph is a DeBruijn graph.

10. The method of claim 8 , wherein the location in the graph for each of a plurality of hosts is determined using a pseudo-random function.

11. The method of claim 10 , wherein the location in the graph for each of a plurality of hosts is determined using the pseudo-random function based on a shared key, the round counter, and an identifier for each of the plurality of hosts.

12. The method of claim 8 , wherein the message sent to the monitor host identifying a value of the round counter is signed.

13. The method of claim 8 , further comprising generating an alert in response to determining whether any received messages are invalid.

14. The method of claim 8 , further comprising determining whether any heartbeat messages were received early.

15. A non-transitory computer-readable medium containing computer-executable instructions that, when executed by a processor, cause the processor to perform a method for defending a computing system from attack, the method comprising:

maintaining a round counter that tracks a round number for a local host;

determining whether the round counter is divisible by a diameter of a graph identifying each of a plurality of hosts including the local host;

in response to determining that the round counter is divisible by the diameter of the graph, determining a location in the graph for each of the plurality of hosts including the local host;

determining a monitor host of the plurality of hosts that is monitoring the local host;

determining a monitoree host of the plurality of hosts that is monitored by the local host;

sending a message to the monitor host identifying a value of the round counter;

forwarding a first set of heartbeat messages from the monitoree host to the monitor host;

attempting to receive a message from the monitoree host;

determining whether a message was not received from the monitoree host; and

in response to determining that a message was not received from the monitoree host, generating an alert.

16. The non-transitory computer-readable medium of claim 15 , wherein the directed graph is a DeBruijn graph.

17. The non-transitory computer-readable medium of claim 15 , wherein the location in the graph for each of a plurality of hosts is determined using a pseudo-random function.

18. The non-transitory computer-readable medium of claim 17 , wherein the location in the graph for each of a plurality of hosts is determined using the pseudo-random function based on a shared key, the round counter, and an identifier for each of the plurality of hosts.

19. The non-transitory computer-readable medium of claim 15 , wherein the message sent to the monitor host identifying a value of the round counter is signed.

20. The non-transitory computer-readable medium of claim 15 , wherein the method further comprises generating an alert in response to determining whether any received messages are invalid.

Continuity (4)
Continuation 17698751 · Mar 18, 2022
Continuation 16365268 · Mar 26, 2019
Provisional Application 62648290 · Mar 26, 2018
Related Publication 20240039941A1 · Feb 1, 2024
References Cited (57)
US H1814H · Browning · 1999 [cited by examiner]
US 7624448B2 · Coffman · 2009 [cited by applicant]
US 7949785B2 · Alkhatib et al. · 2011 [cited by applicant]
US 8627473B2 · Coskun · 2014 [cited by applicant]
US 9231936B1 · Wang · 2016 [cited by examiner]
US 9495544B2 · Aissi · 2016 [cited by examiner]
US 9876808B2 · Lim et al. · 2018 [cited by applicant]
US 9886581B2 · Olson et al. · 2018 [cited by applicant]
US 9928366B2 · Ladnai et al. · 2018 [cited by applicant]
US 10168697B2 · Hernandez Sanchez et al. · 2019 [cited by applicant]
US 10609005B2 · Iizuka · 2020 [cited by examiner]
US 11025483B1 · Hashmi · 2021 [cited by applicant]
US 11556658B2 · Schvey · 2023 [cited by examiner]
US 20090293122A1 · Abdel-Aziz · 2009 [cited by applicant]
US 20130305357A1 · Ayyagari et al. · 2013 [cited by applicant]
US 20140136414A1 · Abhyanker · 2014 [cited by applicant]
US 20150341422A1 · Farnlof · 2015 [cited by applicant]
US 20160156611A1 · Rozman · 2016 [cited by applicant]
US 20180032724A1 · Tang et al. · 2018 [cited by applicant]
US 20180077174A1 · Herbert · 2018 [cited by applicant]
US 20180089014A1 · Smith · 2018 [cited by applicant]
US 20180183827A1 · Zorlular et al. · 2018 [cited by applicant]
US 20240305654A1 · Diehl · 2024 [cited by examiner]
Al-Riyami et al (“An Adaptive Early Node Compromise Detection Scheme for Hierarchical WSNs”), IEEE Access, Digital Object Identifier 10.1109/ACCESS.2016.2594478, Aug. 3, 2016, pp. 4183-4206 (Year: 2016). [cited by examiner]
Dutta et al (“Asynchronous Neighbor Discovery: Finding Needles of Connectivity in Haystacks of Time”), IEEE, 2008 International Conference on Information Processing in Sensor Networks (ipsn 2008), Apr. 22-24, 2008, pp. … [cited by examiner]
Liang et al (“Collision Resolution Algorithm-Based Heartbeat Radio Access”), 2010 IEEE Aerospace Conference, The Aerospace Corporation, IEEE Xplore, pp. 1-6 (Year: 2010). [cited by examiner]
Fraigniaud et al (“D2B: A de Bruijn based content—addressable network”), Science Direct, Theoretical Computer Science 355 (2006) , pp. 65-79 (Year: 2006). [cited by examiner]
Chang, H., and Atallah, M.J., “Protecting Software Code by Guards”, In Digital Rights Management Workshop, May 7, 2002, pp. 160-175. [cited by applicant]
Chinchani, R., et al., “A Tamper-Resistant Framework for Unambiguous Detection of Attacks in User Space Using Process Monitors”, In the Proceedings of the First IEEE International Workshop on Information Assurance, Darm… [cited by applicant]
Cluley, G., “DarkSeoul: SophosLabs identifies malware used in South Korean internet attack”, Naked Security by Sophos, Mar. 20, 2013, available at: https://nakedsecurity.sophos.com/2013/03/20/south-korea-cyber-attack, p… [cited by applicant]
Coppolino, L. et al., “A Trusted Information Agent for Security Information and Event Management”, In ICONS 2012, The Seventh International Conference on Systems, Feb. 29-Mar. 5, 2012 Saint Gilles, Reunion Island, pp. 6… [cited by applicant]
Ernst, J., et al., “A Survey and Comparison of Performance Evaluation in Intrusion Detection Systems”, In Computer and Network Security Essentials, Aug. 2017, pp. 555-568. [cited by applicant]
Gupta, I., et al., “On Scalable and Efficient Distributed Failure Detectors”, In Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, Aug. 1, 2001, pp. 170-179. [cited by applicant]
Jabez, J., et al., “Intrusion Detection System (IDS): Anomaly Detection Using Outlier Detection Approach”, In Procedia Computer Science, Jun. 2015, pp. 338-346. [cited by applicant]
Janakiraman, R., et al., “Indra: a peer-to-peer approach to network intrusion detection and prevention”, In the Proceedings of the Twelfth IEEE International Workshops on Enabling Technologies: Infrastructure for Collab… [cited by applicant]
Kaashoek, M., et al., “Koorde: A Simple Degree-Optimal Distributed Hash Table”, In Proceedings of Internation Workshop on Peer-to-Peer Systems, Lecture Notes in Computer Science, vol. 2735, Feb. 21-22, 2003, pp. 98-107. [cited by applicant]
Karspersky Lab, “How to Enable/Disable Self-Defense of Kaspersky Internet Security 2012”, Aug. 15, 2012, available at http://support.kaspersky.com/6259, pp. 1-6. [cited by applicant]
Kaufman, D., “An Analytical Framework for Cyber Security” Technical Report, Nov. 2011, pp. 1-24. [cited by applicant]
Malkhi, D., et al., “Unreliable Intrusion Detection in Distributed Computations”, In Proceedings 10th Computer Security Foundations Workshop, Jun. 10-12, 1997, Rockport, MA, US, pp. 116-124. [cited by applicant]
Mohamed, N., et al., “A Fault Tolerant Wired/Wireless Sensor Network Architecture for Monitoring Pipeline Infrastructures”, In 2008 Second International Conference on Sensor Technologies and Applications, Aug. 25-31, 20… [cited by applicant]
Notice of Allowance dated Jul. 20, 2023 in U.S. Appl. No. 17/698,751, pp. 1-56. [cited by applicant]
Notice of Allowance dated Dec. 22, 2021 in U.S. Appl. No. 16/365,268, pp. 1-19. [cited by applicant]
NS-3, “ns-3 Network Simulator,” Jun. 2014, available at: https://nsnam.org, pp. 1-121. [cited by applicant]
Office Action dated Mar. 23, 2023 in U.S. Appl. No. 17/698,751, pp. 1-237. [cited by applicant]
Office Action dated Jun. 25, 2021 in U.S. Appl. No. 16/365,268, pp. 1-15. [cited by applicant]
Paxson, V., “Bro: A system for detecting network intruders in real-time,” USENIX Security Symposium, San Antonio, Texas, US, Jan. 26-29, 1998, pp. 1-22. [cited by applicant]
Perlroth, N., et al., “How Israel Caught Russian Hackers Scouring the World for U.S. Secrets”, In The New York Times, Oct. 10, 2017, available at:https://www.nytimes.com/2017/10/10/technology/kaspersky-lab-israel-russia… [cited by applicant]
Plummer, D. W., et al., “The History of Nuclear Weapon Safety Devices”, Sandia National Laboratories. Jun. 8, 1998, pp. 1-8. [cited by applicant]
Skywing, “Patchguard Reloaded: A Brief Analysis of Patchguard Version 3”, Sep. 2007, available at www.uninformed.org/?v=8&a=5&t=txt, pp. 1-2. [cited by applicant]
Spray, S. and Cooper, A., “The Unique Signal Concept for Detonation Safety in Nuclear Devices”, Technical Report UC-706, Sandia National Laboratories, Dec. 1992, pp. 1-73. [cited by applicant]
Stolfo, S.J., et al., “Self-Monitoring Monitors”, Technical Report, CUCS-026-09, Columbia University Computer Science Department, Apr. 2009, pp. 1-11. [cited by applicant]
Sun, Q., “Improving the Performance of Peer-to-Peer Systems”, Technical Report, Dissertation, Stanford University, Sep. 2009, pp. 1-201. [cited by applicant]
Symantec Corporation, “Symantec Endpoint Protection 11.0: Configuring the sep client for self-protection”, available at http://www.symantec.com/connect/sites/default/files/SEP_Protecting_SEP_ Client_rev1.0.pdf, 2011, la… [cited by applicant]
Yang, Y., et al., “Distributed Software-based Attestation for Node Compromise Detection in Sensor Networks”, In 2007 26th IEEE International Symposium on Reliable Distributed Systems, Oct. 10-12, 2007, Beijing, China, p… [cited by applicant]
Yi, S., et al., “Research of Network Intrusion-Detection System Based on Data Mining”, In Recent Progress in Data Engineering and Internet Technology, Apr. 2012, pp. 141-148. [cited by applicant]
Yuan, F., et al., “Research Intrusion Detection System on Android”, In the Proceedings of the IEEE Ninth World Congress on Services, Santa Clara, CA, US, Jun. 28-Jul. 3, 2013, pp. 312-316. [cited by applicant]
Zhou, C., et al., “A Survey of Coordinated Attacks and Collaborative Intrusion Detection”, In Computers and Security, vol. 29, No. 1, Feb. 2010, pp. 124-140. [cited by applicant]