A flow information analysis apparatus receives flow information containing a header sample, determines whether the header sample of the flow information matches any of templates that are based on tunneling protocols, and when determining that the header sample matches any of the templates, extract information on a header of the IP packet from the header sample on the basis of the matched template. Further, when determining that the header sample does not match any of the templates, the flow information analysis apparatus extracts information on the header of the IP packet from the header sample on the basis of a result of a search through the header sample for a byte sequence that matches search data in which a value that is set in a specific field of the tunnel header and a value that is set in a specific field of the IP packet are combined.