Systems and methods for implementing a cooperative security fabric (CSF) protocol are provided. According to one embodiment, a CSF of multiple network security devices (NSDs) deployed within a protected network is constructed in a form of a tree, having a root node, one or more intermediate nodes and one or more leaf nodes, based on hierarchical interconnections among the NSDs by determining a relative upstream or downstream relationship among each NSD. Backend daemons of the NSDs establish and maintain a bi-directional tunnel between each parent node within the CSF and its respective child nodes through which queries and replies are communicated and through which periodic keep-alive messages and responses are exchanged. Forward daemons of the NSDs enforce a CSF protocol that limits the issuance of query messages to those originated by an upstream node within the CSF and directed to a downstream node within the CSF.