Friam

Research on weakest points in hierarchical networks

Classic

List

Threaded

4 messages Options

Parks, Raymond

Research on weakest points in hierarchical networks

Folks,

We've run across something here at Sandia to which we have a gut
reaction but we're looking for research to support that reaction.

We frequently assess networks that perform in an hierarchical
fashion. Data flows on these networks from some command or control
level through various intermediate nodes to individual leaf nodes.
Usually, there's far more leaf nodes than command or control level
nodes, so the data path is "diluted" out to the leaf nodes. There are
return paths, although not necessarily the same, in which small amounts
of data from each leaf node are combined and multiplexed all the way
back up to the command or control nodes.

Our belief is that an attacker can have the greatest effect on the
entire process by modifying data somewhere in an intermediate node. An
attack at a command or control node is ameliorated because the data
spreads out to a large number of leaf nodes. An attack at a leaf node
is inconsequential because that node's data contribution is lost when
aggregated with all the other leaf nodes. A purely informal proof (that
harks back to the recent discussion of entropy) is that if one considers
Shannon's theory of information entropy, the least distance to an
information source is a middle node of the network. However, that's
really informal and speculative.

Does anyone out there know of any research that might prove or
disprove our hypothesis that a middle node can have the greatest effect?

--
Ray Parks [hidden email]
IDART Project Lead Voice:505-844-4024
IORTA Department Fax:505-844-9641
http://www.sandia.gov/idart Pager:800-690-5288

Stephen Guerin

Research on weakest points in hierarchical networks

Partially related is the research from 4 or 5 years ago on percolation and
robustness in Small World and Scale Free networks which I'm sure you guys
are aware of and probably contributed to.

I haven't seen anything more specific to attacking the data content in
hierarchical networks. Though, empirically, it would be pretty
straightforward to write a model and sweep the parameter space to quickly
test your intuitions of intermediate node vulnerabilities.

BTW, from you description, I'm a little unclear why a command or control
node (top of the hierarchy) wouldn't be a more vulnerable target than an
intermediate node. Wouldn't a modification of data at the source have the
greatest impact? Or in other words, a source node by definition has the
smallest distance to the information source. I must be missing a key idea in
the model description. It may be that you're talking about something
different than a command and control network and more of a
"Perceiving/Acting" network where information integration is happening in
the intermediate nodes. Perceiving/Acting networks isn't a standard term for
graph theory; I'm applying it from the Ecological Psychology literature.

-Steve

______________________________________________________
[hidden email] office: (505)995-0206
http://www.redfish.com mobile: (505)577-5828

> -----Original Message-----
> From: Raymond C. Parks [mailto:[hidden email]]
> Sent: Friday, December 17, 2004 6:10 PM
> To: The Friday Morning Complexity Coffee Group
> Cc: Berg, Michael J
> Subject: [FRIAM] Research on weakest points in hierarchical networks
>
>
> Folks,
>
> We've run across something here at Sandia to which we have a gut
> reaction but we're looking for research to support that reaction.
>
> We frequently assess networks that perform in an hierarchical
> fashion. Data flows on these networks from some command or control
> level through various intermediate nodes to individual leaf nodes.
> Usually, there's far more leaf nodes than command or control level
> nodes, so the data path is "diluted" out to the leaf nodes. There are
> return paths, although not necessarily the same, in which small amounts
> of data from each leaf node are combined and multiplexed all the way
> back up to the command or control nodes.
>
> Our belief is that an attacker can have the greatest effect on the
> entire process by modifying data somewhere in an intermediate node. An
> attack at a command or control node is ameliorated because the data
> spreads out to a large number of leaf nodes. An attack at a leaf node
> is inconsequential because that node's data contribution is lost when
> aggregated with all the other leaf nodes. A purely informal proof (that
> harks back to the recent discussion of entropy) is that if one considers
> Shannon's theory of information entropy, the least distance to an
> information source is a middle node of the network. However, that's
> really informal and speculative.
>
> Does anyone out there know of any research that might prove or
> disprove our hypothesis that a middle node can have the greatest effect?
>
> --
> Ray Parks [hidden email]
> IDART Project Lead Voice:505-844-4024
> IORTA Department Fax:505-844-9641
> http://www.sandia.gov/idart Pager:800-690-5288
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9AM @ Jane's Cafe
> Lecture schedule, archives, unsubscribe, etc.:
> http://www.friam.org
>
>

Gus Koehler

Research on weakest points in hierarchical networks

A slightly different perspective on the problem may yield surprising results
along the lines suggested.

-- Assume that each node or hub has its own characteristic processing time
that is strictly local except for hub connections before it forwards the
message or responds to it;
-- Hubs and nodes evolve their capacities to process information at varying
rates; and
-- that the connections, pipes also vary in processing time, evolve, etc.
-- These basic assumptions would change the way the network functions.
Perhaps, slow processing hubs could lag behind or be driven by multiple
intermediate sized nodes that process much faster and have high speed links.
There could be a characteristic wave (soluton like) for the network.

This is simulation stuff. Visualization would be really important but would
be subject to many of the self delusions made in Stephen's video and more.

Personally, I think this would be closer to "life" particularly if the
network is embedded in some sort of information ecology and all that that
means for processing for the network of interest.

Gus

Gus Koehler, Ph.D.
Principal
Time Structures
1545 University Ave.
Sacramento, CA 95825
916-564-8683
Fax: 916-564-7895
www.timestructures.com

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf
Of Stephen Guerin
Sent: Saturday, December 18, 2004 2:07 PM
To: The Friday Morning Applied Complexity Coffee Group
Cc: Berg, Michael J
Subject: RE: [FRIAM] Research on weakest points in hierarchical networks

Partially related is the research from 4 or 5 years ago on percolation and
robustness in Small World and Scale Free networks which I'm sure you guys
are aware of and probably contributed to.

I haven't seen anything more specific to attacking the data content in
hierarchical networks. Though, empirically, it would be pretty
straightforward to write a model and sweep the parameter space to quickly
test your intuitions of intermediate node vulnerabilities.

BTW, from you description, I'm a little unclear why a command or control
node (top of the hierarchy) wouldn't be a more vulnerable target than an
intermediate node. Wouldn't a modification of data at the source have the
greatest impact? Or in other words, a source node by definition has the
smallest distance to the information source. I must be missing a key idea in
the model description. It may be that you're talking about something
different than a command and control network and more of a
"Perceiving/Acting" network where information integration is happening in
the intermediate nodes. Perceiving/Acting networks isn't a standard term for
graph theory; I'm applying it from the Ecological Psychology literature.

-Steve

______________________________________________________
[hidden email] office: (505)995-0206
http://www.redfish.com mobile: (505)577-5828

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9AM @ Jane's Cafe
Lecture schedule, archives, unsubscribe, etc.:
http://www.friam.org

Parks, Raymond

Research on weakest points in hierarchical networks

In reply to this post by Stephen Guerin

Stephen Guerin wrote:

> Partially related is the research from 4 or 5 years ago on percolation and
> robustness in Small World and Scale Free networks which I'm sure you guys
> are aware of and probably contributed to.

I am aware of it, but I did not contribute to that work. However,
these networks aren't really either Small World or Scale Free. They are
clearly hierarchical even though some communication is via other
networks that are Small World.

> I haven't seen anything more specific to attacking the data content in
> hierarchical networks. Though, empirically, it would be pretty
> straightforward to write a model and sweep the parameter space to quickly
> test your intuitions of intermediate node vulnerabilities.

What would you use to write such a model? I'm not in the modeling
business, normally, but I could be if necessary.

> BTW, from you description, I'm a little unclear why a command or control
> node (top of the hierarchy) wouldn't be a more vulnerable target than an
> intermediate node. Wouldn't a modification of data at the source have the
> greatest impact? Or in other words, a source node by definition has the
> smallest distance to the information source. I must be missing a key idea in
> the model description. It may be that you're talking about something
> different than a command and control network and more of a
> "Perceiving/Acting" network where information integration is happening in
> the intermediate nodes. Perceiving/Acting networks isn't a standard term for
> graph theory; I'm applying it from the Ecological Psychology literature.

You've hit the nail on the head with your last suggestion. We are
looking at networks that transform the data during its move from the
command or control nodes out to the leaf nodes. The data is changed
from generalities to specifics. The intermediate nodes modify commands
enough that an attack on the command or control nodes is watered down by
the intermediate transformations. Conversely, the leaf nodes only have
a very small part of the total data picture. They transmit information
up the hierarchy and the intermediate nodes consolidate, aggregate, and
create new data from what the leaf nodes transmit. An attack on a leaf
node is able to affect the world of that leaf node. In a few rare
cases, the data from the leaf node may make it to the command or control
node level without change and thus affect decisions made at that level.
However, in the majority of cases, the data transformation is
sufficient that a data attack is hidden in the background by the time
data makes it to the command or control nodes.

Thanks for the pointer. I will set our reference librarian searching
for Perceiving/Acting networks in the Ecological Psychology literature.

--
Ray Parks [hidden email]
IDART Project Lead Voice:505-844-4024
IORTA Department Fax:505-844-9641
http://www.sandia.gov/idart Pager:800-690-5288