How does an entity on a network (e.g. sysadmin, security software) identify that a user is connecting to the internet with a proxy?

Question

For example, the security software iBoss is able to detect if you are using a proxy.

Proxy Circumvention

Proxy attempts to circumvent your Internet security solution not only violate your organization’s policies, they are potential avenues for delivering advanced threats such as viruses, botnets and malware. iboss offers a multi-layered approach to defending against proxies and proxy applications such as Ultrasurf, Hotspot shield and others:

What I am wondering is how does this detection work? Does it look for headers in your request(s)? Does it analyze traffic patterns? Does it detect communication over specific ports?

Answer 1

For standard HTTP proxies it is enough to look at the first bytes of each TCP connection, which means it can already be detected without doing too deep inspection. A HTTP proxy requests looks different from a normal HTTP request, i.e.

 non-proxy: GET / HTTP/1.1
 proxy:     GET http://example.com/ HTTP/1.1

You have similar differences for HTTPS, where a non-proxy connection starts with the ClientHello from the TLS handshake while a HTTP proxy connection starts with the use of a CONNECT method. SOCKS proxies similarly can be detected when looking at the first few bytes from the client.

For other kinds of special (non-standard) proxy protocols or for VPN solutions they probably simply detect and block access to specific destination IP and port, see How to Detect and Block UltraSurf program traffic and How to Detect and Block Hotspot Shield program traffic(openvpn application).

I'm pretty sure that you will be able to circumvent these detection by using your own tunnels, i.e. tunneling through SSH or using tools like http tunnel. But, initial circumvention attempts by most users will probably be detected and if you punish policy violations hard enough most users will not try again with a different circumvention technology.

... they are potential avenues for delivering advanced threats such as viruses, botnets and malware

This effectively means that by allowing arbitrary connections to the internet you increase the chance of getting infected by malvertisement or hacked or otherwise malicious web sites. This is definitely true.

And once the malware is inside most products will probably not help much to detect the CnC communication of the malware because the malware uses their own protocols or built their CnC communication based on public sites. To cite from a report by FireEye 2013 "Malware Callbacks":

To evade detection, CnC servers are leveraging social networking sites like Facebook and Twitter for communicating with infected machines. Also, to mask exfiltrated content, attackers embed information inside common files, such as JPGs, to give network scanning tools the impression of normal traffic.