{"action":"created","issue":{"url":"https://api.github.com/repos/GGist/bip-rs/issues/41","repository_url":"https://api.github.com/repos/GGist/bip-rs","labels_url":"https://api.github.com/repos/GGist/bip-rs/issues/41/labels{/name}","comments_url":"https://api.github.com/repos/GGist/bip-rs/issues/41/comments","events_url":"https://api.github.com/repos/GGist/bip-rs/issues/41/events","html_url":"https://github.com/GGist/bip-rs/issues/41","id":145415392,"number":41,"title":"Bencode Parser Vulnerability/Level 3 Parser","user":{"login":"GGist","id":5248583,"avatar_url":"https://avatars.githubusercontent.com/u/5248583?v=3","gravatar_id":"","url":"https://api.github.com/users/GGist","html_url":"https://github.com/GGist","followers_url":"https://api.github.com/users/GGist/followers","following_url":"https://api.github.com/users/GGist/following{/other_user}","gists_url":"https://api.github.com/users/GGist/gists{/gist_id}","starred_url":"https://api.github.com/users/GGist/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/GGist/subscriptions","organizations_url":"https://api.github.com/users/GGist/orgs","repos_url":"https://api.github.com/users/GGist/repos","events_url":"https://api.github.com/users/GGist/events{/privacy}","received_events_url":"https://api.github.com/users/GGist/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/GGist/bip-rs/labels/bip","name":"bip","color":"006b75"},{"url":"https://api.github.com/repos/GGist/bip-rs/labels/Bug","name":"Bug","color":"fc2929"},{"url":"https://api.github.com/repos/GGist/bip-rs/labels/Optimization","name":"Optimization","color":"5319e7"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":2,"created_at":"2016-04-02T20:27:36Z","updated_at":"2016-04-14T19:20:36Z","closed_at":null,"body":"Currently our lazy bencode parser uses recursion to decode and encode data. This makes it trivial for anyone to crash one of the applications using ```bip_bencode``` where the data is coming off the network. With a maximum stack of say 80 stack frames, they could crash our services using a minimum of 160 bytes (ex: just nest a bunch of lists, ```l l l l l l ... e e e e e e```).\r\n\r\nThe obvious solution is to implement an iterative decoder/encoder. However, since we are already introducing complexity into the ```bip_bencode``` module by doing so, we could also reach for yet another performance boost in terms of our implementation.\r\n\r\nWhat we used to have implemented was a level 1 bencode parser where all dictionary keys and byte arrays were allocated on the heap. We then moved to a level 2 bencode parser where those two structures were just references, but we still allocated bencode lists and dictionaries on the heap. LibTorrent has a [nice blog post](http://blog.libtorrent.org/2015/03/bdecode-parsers/) where they go over the implementation of a level 3 bencode parser that has both a borrowed list of bytes, as well as a (heap allocated) list of tokens pointing into the list of bytes.\r\n\r\nThe benefit that a level 3 bencode parser brings is that we get great token locality as well as amortized heap allocations since we are using a single (fairly small) heap allocated structure instead of many small ones. We can also see that encoding is as easy as returning the already made list of bytes (essentially a noop). The downside is we have to copy data used in our macros to that list of bytes and make corresponding tokens for them. However, we may be able to pre compute the needed pre allocation capacity for macro related bencode construction (depends on what macros allow). Additonally, dictionary searching goes down to (at best) log n retrival speed instead of constant depending on if we want to store key offsets and inserting ANYTHING into an already made structure will push (potentially many) bytes back which could get expensive depending on the usage patterns. For this reason, we may want to keep the current implementation and just add the new implementation as the current implementation is great at cheaply inserting data into an already made bencode structure.\r\n\r\nWill benchmark against the current implementation to see the kind of performance boost we get to see if it is worth it or not.\r\n\r\nEdit: Vulnerability only requires the list/dictionary to be started which means ```l l l l l ...``` would suffice meaning a maximum of 80 stack frames requires a minimum of 80 bytes."},"comment":{"url":"https://api.github.com/repos/GGist/bip-rs/issues/comments/210108641","html_url":"https://github.com/GGist/bip-rs/issues/41#issuecomment-210108641","issue_url":"https://api.github.com/repos/GGist/bip-rs/issues/41","id":210108641,"user":{"login":"GGist","id":5248583,"avatar_url":"https://avatars.githubusercontent.com/u/5248583?v=3","gravatar_id":"","url":"https://api.github.com/users/GGist","html_url":"https://github.com/GGist","followers_url":"https://api.github.com/users/GGist/followers","following_url":"https://api.github.com/users/GGist/following{/other_user}","gists_url":"https://api.github.com/users/GGist/gists{/gist_id}","starred_url":"https://api.github.com/users/GGist/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/GGist/subscriptions","organizations_url":"https://api.github.com/users/GGist/orgs","repos_url":"https://api.github.com/users/GGist/repos","events_url":"https://api.github.com/users/GGist/events{/privacy}","received_events_url":"https://api.github.com/users/GGist/received_events","type":"User","site_admin":false},"created_at":"2016-04-14T19:20:36Z","updated_at":"2016-04-14T19:20:36Z","body":"Since I may not get around to tackling the L3 parser soon, I went ahead and converted the existing parser to an iterative parser.\r\n\r\nTested the **old** parser with ```bip_dht``` and confirmed that stack overflows where occuring when sending 800 bytes of ```l```s to the service. Confirmed that with the **new** parser, this is no longer an issue.\r\n\r\nHowever, benchmarks are showing that the recursive parser was modestly faster.\r\n\r\nParsing 100 Nested Lists\r\n--------------------------------\r\n\r\n**With Opt 0**\r\nIterative: 36,200 ns\r\nRecursive: 28,100 ns\r\n\r\n**With Opt 3**\r\nIterative: 25,000 ns\r\nRecursive: 17,000 ns\r\n\r\nParsing A 2KB Torrent File\r\n----------------------------------\r\n\r\n**With Opt 0**\r\nIterative: 120,600,000 ns\r\nRecursive: 82,400,000 ns\r\n\r\n**With Opt 3**\r\nIterative: 95,400,000 ns\r\nRecursive: 56,100,000 ns\r\n\r\nIt looks like the compiler isn't optimizing the old version anymore than the new version, so I guess it comes down to us really doing more work in the new version which makes sense. To make the code simple, when we find any type, we push it on the stack and deal with it on the next iteration. This means for non-recursive types, we are always iterating twice instead of once. Additionally, we have a TON of match arms both when dealing with the item on the top of the stack, and when collapsing types which leads to a ridiculous amount of branching compared to the first implementation. I don't see any way around this which is interesting and leads me to the conclusion that for recursively defined text formats such as bencode, recursive parsers will almost always have an upper hand both in simplicity and performance.\r\n\r\nNow that I know that excessive matching really kills performance, I am going to think about how to take advantage of the properties of an L3 parser in order to avoid that.\r\n\r\n"}}