Systems, methods and apparatus for tunneling in a cloud based security system. In an aspect, tunnel session data describing authentication and unauthenticated sessions, and location data describing tunnel identifiers for tunnels, locations, and security policies specific to the locations are accessed. Tunnel packets are received, and for each tunnel packet it is determined, from the tunnel identifier associated with the packet, whether a session entry in the session data exists for the tunnel identified by the tunnel identifier. In response to determining that a session entry does not exist in the session data, then a session entry is created for the tunnel identifier, an authentication process to determine a location to be associated with the session entry is performed, and an entry in the location data for the location is associated with the session entry.