Android - In Android 6, how to deny an app permission to access the network?

You won't be able to achieve success through the native mechanism of Android.

Cody Toombs at Android Police has very well pointed this out in the article: Android M Will Never Ask Users For Permission To Use The Internet, And That's Probably Okay.

In the section Normal and Dangerous Permissions of the document Permissions Overview, Google has noted:

Permissions are divided into several protection levels.

There are two protection levels that affect thrid party apps: normal and dangerous permissions.

• Normal permissions cover areas where your app needs to access data or resources outside the app's sandbox, but where there's very little risk to the user's privacy or the operation of other apps. For example, permission to set the time zone is a normal permission.

  If an app declares in its manifest that it needs a normal permission, the system automatically grants the app that permission at install time. The system does not prompt the user to grant normal permissions, and users cannot revoke these permissions.

• Dangerous permissions cover areas where the app wants data or resources that involve the user's private information, or could potentially affect the user's stored data or the operation of other apps. For example, the ability to read the user's contacts is a dangerous permission. If an app declares that it needs a dangerous permission, the user has to explicitly grant the permission to the app.

_{(Emphasis mine)}

Surprising or not, the following permissions comes under the list of Normal Permissions:

• CHANGE_NETWORK_STATE - allows applications to change network connectivity state - i.e. mobile data;
• CHANGE_WIFI_STATE - allows applications to change Wi-Fi connectivity state;
• INTERNET - allows applications to open network sockets.

If that doesn't suffice, checkout the permissions managed by AppOps here. If you don't find your permission listed there, you won't be able to do anything with it in GUI.

Since alternative methods are already extensively covered on this site, refer to:

• Block apps from accessing the Internet on Android device
• Are there any tools to sandbox a malware application even more than the granted permissions on Android?

You could use NetGuard (see my list of Internet Firewalls for other alternatives), which works without root and lets you block internet access for apps selectively (WiFi or mobile data, and even always or only if screen is off). It's from the dev of XPrivacy, so it has to be good ;)

^{NetGuard (source: Google Play; click images for larger variants)}

NetGuard is open source, so you can also find it at F-Droid.

Update: Note that recent versions of Netguard include Google Ads as well as Firebase Analytics – two things which IMHO have no business in a firewall (or any other security) application – which most likely is the reason it is no longer updated on F-Droid's official repo (still available in mine with the appropriate warnings).

There are some really cool apps that can do it without rooting. Here are two examples:

• LostNet Firewall Free:

  _{(Click image to enlarge)}

  

• Mobiwol: NoRoot Firewall

  _{(Click image to enlarge)}