I was under impression that allowing icmp in the service policy will enable tracert to work. I was wrong. After scouting around I found below tweaks that will enable tracert to run correctly.

1. Set decrement TTL
ASA# configure terminal
ASA(config)# policy-map global_policy
ASA(config-pmap)# class class-default
ASA(config-pmap-c)# set connection decrement-ttl
ASA(config-pmap-c)# exit

2. Permit icmp control messages
ASA(config)# access-list inbound permit icmp any any time-exceeded
ASA(config)# access-list inbound permit icmp any any unreachable

3. Permit icmp connection, which you should already have 😀
ASA(config)# access-list outbound permit icmp any any

References:
http://www.cisco.com/c/en/us/td/docs/ios/sec_data_plane/configuration/guide/12_4/sec_data_plane_12_4_book/sec_fwall_icmp_insp.html

http://www.petenetlive.com/KB/Article/0000753.htm

Incoming search terms:

• allow tracert asa
• cisco asa 5505 policy map icmp
• Cisco ASA 5525X allowing trace route