Client Certificates are the best way to go.
You can use API Gateway to generate an SSL certificate and use its
public key in the backend to verify that HTTP requests to your backend
system are from API Gateway. This allows your HTTP backend to control
and accept only requests originating from Amazon API Gateway, even if
the backend is publicly accessible.
Think of it as inverting the typical role of an SSL certificate (which currently verifies that the HTTP response you're viewing came from StackOverflow.com.)
Instead, you'll use this client certificate to verify in your microservices' HTTP layers that the request came from your API Gateway. To do this, generate a Client Certificate for your API gateway. Then, retrieve the PEM-encoded public key from the same interface, and configure your HTTP server to only accept connections which are encrypted with this client certificate.
This article appears to describe how to configure Tomcat to accept / enforce client certificates: http://www.maximporges.com/2009/11/18/configuring-tomcat-ssl-clientserver-authentication/
clientAuth="true" port="8443" minSpareThreads="5" maxSpareThreads="75"
scheme="https" secure="true" SSLEnabled="true"
SSLVerifyClient="require" SSLEngine="on" SSLVerifyDepth="2" sslProtocol="TLS"
A less robust option, rather than SSL Client Certificates, might be to add "secret" API keys, e.g. as request headers or query parameters, to all requests from your API Gateway. Your microservices can then look for this API key as indication that the request came from your API Gateway and should be trusted / accepted.