News for hackers. Stuff that matters.

A comment on New ‘Meow’ attack has deleted almost 4k unsecured databases. Parent comment

Re:New ‘Meow’ attack has deleted almost 4k unsecured databases by red0point on Sunday July 26, 2020 @02:59PM (#23959286)
1) If it‘s a tree, it ain‘t got no loops 2) The stack isn‘t to deal with loops, the „visited“ flag at each edge is there for that. The stack (for DFS, BFS would be a queue) is there to keep track of which nodes have been visited such that you can construct a path from the starting node to the one you‘re looking for.

Obviously there are variants to this, depending on what you‘re actually trying to achieve with it. My point is that a stack would be a very inefficient way to deal with loops.

[ Parent | on HN ]
Re:New ‘Meow’ attack has deleted almost 4k unsecured databases by hinkley on Sunday July 26, 2020 @03:31PM (#23959521)
Modifying the graph turns it into shared (mutable) state. Your code is still re-entrant, but it's no longer concurrent.
[ Parent | on HN ]
Re:New ‘Meow’ attack has deleted almost 4k unsecured databases by inetknght on Sunday July 26, 2020 @03:17PM (#23959420)
1) you're right, I edited my message to reflect that I meant a graph traversal algorithm.

2) a visited flag on an edge? That won't support simultaneous traversals. Keeping a stack is a lot more efficient than permitting only one traversal at a time.

[ Parent | on HN ]
Re:New ‘Meow’ attack has deleted almost 4k unsecured databases by red0point on Sunday July 26, 2020 @05:34PM (#23960359)
I‘m not sure why you‘re bringing concurrency to the table.

My point still is that looking something up in a stack (did I visit this node?) costs O(n) time, so the BFS will degrade from O(m+n) to O(m*n+n).

To come back to the concurrency, if you can index your edges in some way, you can also store the visited flag in a separate datastracture to support concurrent access (one „flag store“ for each access).

[ Parent | on HN ]
Re:New ‘Meow’ attack has deleted almost 4k unsecured databases by inetknght on Sunday July 26, 2020 @07:59PM (#23961105)
> I‘m not sure why you‘re bringing concurrency to the table.

Not using data structures that enable concurrency prevents performance improvements since modern hardware is, in general, more parallel than vertical.

[ Parent | on HN ]