{"action":"created","issue":{"url":"https://api.github.com/repos/angr/angr/issues/108","repository_url":"https://api.github.com/repos/angr/angr","labels_url":"https://api.github.com/repos/angr/angr/issues/108/labels{/name}","comments_url":"https://api.github.com/repos/angr/angr/issues/108/comments","events_url":"https://api.github.com/repos/angr/angr/issues/108/events","html_url":"https://github.com/angr/angr/issues/108","id":153941680,"number":108,"title":"The caller object eats much memory","user":{"login":"brokendragon","id":16531562,"avatar_url":"https://avatars.githubusercontent.com/u/16531562?v=3","gravatar_id":"","url":"https://api.github.com/users/brokendragon","html_url":"https://github.com/brokendragon","followers_url":"https://api.github.com/users/brokendragon/followers","following_url":"https://api.github.com/users/brokendragon/following{/other_user}","gists_url":"https://api.github.com/users/brokendragon/gists{/gist_id}","starred_url":"https://api.github.com/users/brokendragon/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/brokendragon/subscriptions","organizations_url":"https://api.github.com/users/brokendragon/orgs","repos_url":"https://api.github.com/users/brokendragon/repos","events_url":"https://api.github.com/users/brokendragon/events{/privacy}","received_events_url":"https://api.github.com/users/brokendragon/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2016-05-10T07:35:50Z","updated_at":"2016-05-10T07:37:03Z","closed_at":null,"body":"Hi\r\nI'd like to explore all paths of a give fuction, so I choose the caller object. The tested code is a simple bubble sort, shown as follows.\r\n```\r\n#define BUFF_LEN 6\r\nvoid bubble_sort(char *buff)\r\n{\r\n  for(int i = 0; i < BUFF_LEN - 1; i++)\r\n    for(int j = i + 1; j < BUFF_LEN; j++)\r\n    {\r\n       if(buff[i] > buff[j])\r\n       { \r\n         int tmp = buff[i];\r\n         buff[i] = buff[j];\r\n         buff[j] = tmp;\r\n       }\r\n    }\r\n}\r\n\r\n```\r\nThen length of `buff `is 6, so I suppose there would be thousands of paths at most.\r\nBelow is my testing script.\r\n```\r\nimport angr\r\nb = angr.Project(\"path_explosion\")\r\ncfg = b.analyses.CFGAccurate()\r\ntarget_func = cfg.kb.functions.function(name='bubble_sort')\r\nprint target_func\r\np = b.factory.path()\r\nx = p.state.memory.load(0x1000, 6)\r\nc = b.surveyors.Caller(0x400566, (0x1000, ), start=p)#0x400566 is the entry of bubble_sort \r\nprint tuple(c.iter_returns())\r\nprint c\r\n```\r\n\r\nI installed Angr in a virtual machine. Before running the testing script, 4.1GB physical memory are cost (8GB in total). The memory consumption increases to 8GB in a few seconds, after I launch the script.  After a few minutes, Angr cashes due to memory exhaustion (may be).\r\n\r\nThen I change the length of `buff `into a little bit smaller value, that is 5. Angr gives me result in about 3 minutes as follows (I omitted detailed information of all founded paths for brief).\r\n`<Explorer with paths: 0 active, 0 spilled, 798 deadended, 0 errored, 0 unconstrained, 226 found, 0 avoided, 0 deviating, 0 looping, 0 lost>`\r\n\r\nI suppose that the caller object may eat much memory if there are many paths (thousands?) should be explored.\r\n\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/angr/angr/issues/comments/218081170","html_url":"https://github.com/angr/angr/issues/108#issuecomment-218081170","issue_url":"https://api.github.com/repos/angr/angr/issues/108","id":218081170,"user":{"login":"rhelmot","id":2498805,"avatar_url":"https://avatars.githubusercontent.com/u/2498805?v=3","gravatar_id":"","url":"https://api.github.com/users/rhelmot","html_url":"https://github.com/rhelmot","followers_url":"https://api.github.com/users/rhelmot/followers","following_url":"https://api.github.com/users/rhelmot/following{/other_user}","gists_url":"https://api.github.com/users/rhelmot/gists{/gist_id}","starred_url":"https://api.github.com/users/rhelmot/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rhelmot/subscriptions","organizations_url":"https://api.github.com/users/rhelmot/orgs","repos_url":"https://api.github.com/users/rhelmot/repos","events_url":"https://api.github.com/users/rhelmot/events{/privacy}","received_events_url":"https://api.github.com/users/rhelmot/received_events","type":"User","site_admin":false},"created_at":"2016-05-10T07:37:03Z","updated_at":"2016-05-10T07:37:03Z","body":"There is no way around this. This is known as the \"state explosion problem\" in the literature, and is the reason naive symbolic execution is indefeasible for large applications."}}