Methods and systems for assessing internet exposure of a cloud-based workload are disclosed. A method comprises accessing at least one cloud provider API to determine a plurality of entities capable of routing traffic in a virtual cloud environment associated with a target account containing the workload, querying the at least one cloud provider API to determine at least one networking configuration of the entities, building a graph connecting the plurality of entities based on the networking configuration, accessing a data structure identifying services publicly accessible via the Internet and capable of serving as an internet proxy; integrating the identified services into the graph; traversing the graph to identify at least one source originating via the Internet and reaching the workload, and outputting a risk notification associated with the workload. Systems and computer-readable media implementing the above method are also disclosed.