Q:

What is the right way to get the list of DNS servers responsible for certain host?

I use following steps:

Query A records for host, some servers return NS records in authority section, so I extract them from that section, if any.
Query NS records, extract them from answer section.

The problem is with "subdomains" (CNAME), for example:
> dig www.microsoft.com A
;; ANSWER SECTION:
www.microsoft.com.      696     IN      CNAME   toggle.www.ms.akadns.net.
toggle.www.ms.akadns.net. 119   IN      CNAME   g.www.ms.akadns.net.
g.www.ms.akadns.net.    263     IN      CNAME   lb1.www.ms.akadns.net.
lb1.www.ms.akadns.net.  31      IN      A       65.55.12.249

> dig www.microsoft.com NS
;; ANSWER SECTION:
www.microsoft.com.      619     IN      CNAME   toggle.www.ms.akadns.net.
toggle.www.ms.akadns.net. 42    IN      CNAME   g.www.ms.akadns.net.
g.www.ms.akadns.net.    186     IN      CNAME   lb1.www.ms.akadns.net.

;; AUTHORITY SECTION:
akadns.net.             174     IN      SOA     internal.akadns.net. hostmaster.akamai.com. 1304057105 90000 90000 90000 180

> dig lb1.www.ms.akadns.net A
;; ANSWER SECTION:
lb1.www.ms.akadns.net.  79      IN      A       65.55.12.249

> dig lb1.www.ms.akadns.net NS
;; AUTHORITY SECTION:
akadns.net.             176     IN      SOA     internal.akadns.net. hostmaster.akamai.com. 1304057402 90000 90000 90000 180

As you can see, there are no NS records returned. How to overcome this problem?

A:

Your algorithm is wrong.  Here's the right one.
For each successively shorter superdomain S of the target domain name T, starting with T itself:

Perform an NS lookup on S.  If the answer is not a non-empty resource record set, go to step 3.  Otherwise you have a set of intermediate domain names D[].
Perform A and AAAA lookups on each name in D[].  This will give you a set of IP addresses.  You have your answer.  END.
Optionally perform a SOA lookup on S.  If the answer is a non-empty resource record set, you are about to cross an administrative boundary having found no non-empty NS resource record set thus far.  You may choose, according to exactly what you are trying to find out, to ABEND.

Remember that you have to make queries to your own resolving proxy DNS server, not to the external content DNS servers, so that you get a complete answer rather than a partial one.  Also remember that you have to follow CNAME chains when inspecting responses.  The response to your dig www.microsoft.com. NS query above, for example, is a CNAME chain leading to an empty NS resource record set for lb1.www.ms.akadns.net..

