As mentioned in the comments, this is actually by design, and is how permission chaining works; if you give someone permission to (for example) EXECUTE a procedure and that procedure UPDATE s a table that has the same owner then permission is still granted. This allows administrators to DENYUSER s access to a TABLE but they still have permission to use a VIEW (which might, for example, expose fewer columns), or not allow a USER to UPDATE a table directly but can through a PROCEDURE (as it has additional workflow defined in it).

The method Dan Guzman recommends in their comment is probably the "best" way; change the schema the object is on and ensure that schema is owned by a different USER (or not dbo ).

An alternative method, if you "can't" do this (perhaps moving the object's schema will be a breaking change) would be to use a deferred statement by using sys.sp_executesql ; this will also break the ownership chain.

I demonstrate both in the below, but suggest that the schema solution is the better option:

USE Sandbox;
GO

CREATE USER SomeUser WITHOUT LOGIN;
CREATE USER AnotherUser WITHOUT LOGIN;
GO

CREATE TABLE dbo.SomeTable (ID int,
                            SomeVal varchar(10));
GO

INSERT INTO dbo.SomeTable (ID,
                           SomeVal)
VALUES(1,'abc'),(2,'def');
GO

CREATE PROC dbo.SomeProc @ID int, @SomeVal varchar(10) AS
BEGIN
    SET NOCOUNT ON;

    UPDATE dbo.SomeTable
    SET SomeVal = @SomeVal
    WHERE ID = @ID;
END
GO

DENY INSERT,UPDATE,DELETE ON OBJECT::dbo.SomeTable TO SomeUser;

GRANT EXECUTE ON OBJECT::dbo.SomeProc TO SomeUser;
GRANT EXECUTE ON OBJECT::dbo.SomeProc TO AnotherUser;
GO

EXECUTE AS USER = 'SomeUser';
GO

EXEC dbo.SomeProc 1, 'xyz'; --Works
GO
REVERT;
GO

SELECT *
FROM dbo.SomeTable;
GO

CREATE OR ALTER PROC dbo.SomeProc @ID int, @SomeVal varchar(10) AS
BEGIN
    SET NOCOUNT ON;

    EXEC sys.sp_executesql N'UPDATE dbo.SomeTable SET SomeVal = @SomeVal WHERE ID = @ID;', N'@ID int, @SomeVal varchar(10)', @ID, @SomeVal;

END
GO

EXECUTE AS USER = 'SomeUser';
GO

EXEC dbo.SomeProc 2, 'abc'; --Fails
GO

REVERT;
GO

SELECT *
FROM dbo.SomeTable;
GO

CREATE SCHEMA SomeSchema AUTHORIZATION AnotherUser; --Has a different owner
GO
ALTER SCHEMA SomeSchema TRANSFER dbo.SomeTable;
GO

CREATE OR ALTER PROC dbo.SomeProc @ID int, @SomeVal varchar(10) AS
BEGIN
    SET NOCOUNT ON;

    UPDATE SomeSchema.SomeTable
    SET SomeVal = @SomeVal
    WHERE ID = @ID;
END
GO

EXECUTE AS USER = 'SomeUser';
GO

EXEC dbo.SomeProc 2, 'abc'; --Fails
GO

REVERT;
GO
SELECT *
FROM SomeSchema.SomeTable;
GO
EXECUTE AS USER = 'AnotherUser';
GO

EXEC dbo.SomeProc 2, 'abc'; --Works, as they own the schema
GO

REVERT;
GO
SELECT *
FROM SomeSchema.SomeTable;

GO

DROP PROC dbo.SomeProc;
DROP TABLE SomeSchema.SomeTable;
DROP SCHEMA SomeSchema;
DROP USER SomeUser;
DROP USER AnotherUser;